A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Linear grammars with one-sided contexts and their automaton representation
Tekijät: Alexander Okhotin, Mikhail Barash
Konferenssin vakiintunut nimi: International symposium on latin american theoretical informatics
Julkaisuvuosi: 2014
Journal: Lecture Notes in Computer Science
Sarjan nimi: LNCS
Numero sarjassa: 8392
Vuosikerta: 8392
Aloitussivu: 190
Lopetussivu: 201
Sivujen määrä: 12
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-642-54423-1_17
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.