Where academic tradition
meets the exciting future

You are here: TUCS > PUBLICATIONS > Publication Search > Defining Contexts in Context-F...

Defining Contexts in Context-Free Grammars

Mikhail Barash, Alexander Okhotin, Defining Contexts in Context-Free Grammars. In: Adrian-Horia Dediu, Carlos Martin-Vide (Eds.), Language and Automata Theory and Applications, LNCS 7183, 106–118, Springer, 2012.

http://dx.doi.org/10.1007/978-3-642-28332-1_10

Abstract:

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 \to a \And \before{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.

BibTeX entry:

@INPROCEEDINGS{inpBaOk12a,
  title = {Defining Contexts in Context-Free Grammars},
  booktitle = {Language and Automata Theory and Applications},
  author = {Barash, Mikhail and Okhotin, Alexander},
  volume = {7183},
  series = {LNCS},
  editor = {Dediu, Adrian-Horia and Martin-Vide, Carlos},
  publisher = {Springer},
  pages = {106–118},
  year = {2012},
  keywords = {context-free grammars, conjunctive grammars, context-sensitive grammars, parsing},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication