TY - GEN

T1 - Defining contexts in context-free grammars

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2012/3/12

Y1 - 2012/3/12

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84857809563&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-28332-1_10

DO - 10.1007/978-3-642-28332-1_10

M3 - Conference contribution

AN - SCOPUS:84857809563

SN - 9783642283314

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 106

EP - 118

BT - Language and Automata Theory and Applications - 6th International Conference, LATA 2012, Proceedings

T2 - 6th International Conference on Language and Automata Theory and Applications, LATA 2012

Y2 - 5 March 2012 through 9 March 2012

ER -