Other publication
Linear Grammars with One-Sided Contexts and their Automaton Representation
Authors: Barash M, Okhotin A
Publisher: EDP SCIENCES S A
Publication year: 2015
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Journal name in source: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Journal acronym: RAIRO-THEOR INF APPL
Volume: 49
Issue: 2
First page : 153
Last page: 178
Number of pages: 26
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita/2015004
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.
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.
UTU Research Portal