O2 Muu julkaisu
Linear Grammars with One-Sided Contexts and their Automaton Representation
Tekijät: Barash M, Okhotin A
Kustantaja: EDP SCIENCES S A
Julkaisuvuosi: 2015
Journal: RAIRO: Informatique Théorique et Applications / RAIRO: Theoretical Informatics and Applications
Tietokannassa oleva lehden nimi: RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS
Lehden akronyymi: RAIRO-THEOR INF APPL
Vuosikerta: 49
Numero: 2
Aloitussivu: 153
Lopetussivu: 178
Sivujen määrä: 26
ISSN: 0988-3754
DOI: https://doi.org/10.1051/ita/2015004
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali