@inproceedings{45180b885f4c4c1b8518d9ec8e6ba611,

title = "Linear grammars with one-sided contexts and their automaton representation",

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 σ02-completeness of the finiteness problem for these grammars.",

author = "Mikhail Barash and Alexander Okhotin",

year = "2014",

month = jan,

day = "1",

doi = "10.1007/978-3-642-54423-1_17",

language = "English",

isbn = "9783642544224",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Nature",

pages = "190--201",

booktitle = "LATIN 2014",

address = "Germany",

note = "11th Latin American Theoretical Informatics Symposium, LATIN 2014 ; Conference date: 31-03-2014 Through 04-04-2014",

}