Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review
Conjunctive grammars (Okhotin, 2001) are an extension of the standard context-free grammars with a conjunction operation, which maintains most of their practical properties, including many parsing algorithms. This paper introduces a further extension to the model, which is equipped with quantifiers for referring to the left context, in which the substring being defined does occur. For example, a rule A → a & ◁B defines a string a, as long as it is preceded by any string defined by B. The paper gives two equivalent definitions of the model-by logical deduction and by language equations-and establishes its basic properties, including a transformation to a normal form, a cubic-time parsing algorithm, and another recognition algorithm working in linear space.
Original language | English |
---|---|
Title of host publication | Language and Automata Theory and Applications - 6th International Conference, LATA 2012, Proceedings |
Pages | 106-118 |
Number of pages | 13 |
DOIs | |
State | Published - 12 Mar 2012 |
Event | 6th International Conference on Language and Automata Theory and Applications, LATA 2012 - A Coruna, Spain Duration: 5 Mar 2012 → 9 Mar 2012 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 7183 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 6th International Conference on Language and Automata Theory and Applications, LATA 2012 |
---|---|
Country/Territory | Spain |
City | A Coruna |
Period | 5/03/12 → 9/03/12 |
ID: 41139821