• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Linear Grammars with One-Sided Contexts and Their Automaton Representation

Mikhail Barash, Alexander Okhotin, Linear Grammars with One-Sided Contexts and Their Automaton Representation. In: Alberto Pardo, Alfredo Viola (Eds.), LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings, Lecture Notes in Computer Science 8392, 190–201, Springer, 2014.

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

Abstract:

The paper considers a family of formal grammars that extends linear context-free grammars with an operator for referring to the left context of a substring being defined, as well as with a conjunction operation (as in linear conjunctive grammars). These grammars are proved to be computationally equivalent to an extension of one-way real-time cellular automata with an extra data channel. The main result is the undecidability of the emptiness problem for grammars restricted to a one-symbol alphabet, which is proved by simulating a Turing machine by a cellular automaton with feedback. The same construction proves the $\Sigma^0_2$-completeness of the finiteness problem for these grammars and automata.

BibTeX entry:

@INPROCEEDINGS{inpBaOk14b,
  title = {Linear Grammars with One-Sided Contexts and Their Automaton Representation},
  booktitle = {LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Montevideo, Uruguay, March 31 - April 4, 2014. Proceedings},
  author = {Barash, Mikhail and Okhotin, Alexander},
  volume = {8392},
  series = {Lecture Notes in Computer Science},
  editor = {Pardo, Alberto and Viola, Alfredo},
  publisher = {Springer},
  pages = {190–201},
  year = {2014},
}

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

Publication Forum rating of this publication: level 1

Edit publication