Linear grammars with one-sided contexts and their automaton representation

Standard

Linear grammars with one-sided contexts and their automaton representation. / Barash, Mikhail; Okhotin, Alexander.

In: RAIRO - Theoretical Informatics and Applications, Vol. 49, No. 2, 01.04.2015, p. 153-158.

Research output: Contribution to journal › Article › peer-review

Author

Barash, Mikhail ; Okhotin, Alexander. / Linear grammars with one-sided contexts and their automaton representation. In: RAIRO - Theoretical Informatics and Applications. 2015 ; Vol. 49, No. 2. pp. 153-158.

BibTeX

@article{a9f51198befe47b79aeee82629b288c4,

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 Σ2-completeness of the finiteness problem for these grammars and automata.",

keywords = "Cellular automata, Conjunctive grammars, Context-free grammars, Contexts, Trellis automata, Undecidability.",

author = "Mikhail Barash and Alexander Okhotin",

year = "2015",

month = apr,

day = "1",

doi = "10.1051/ita/2015004",

language = "English",

volume = "49",

pages = "153--158",

journal = "RAIRO - Theoretical Informatics and Applications",

issn = "0988-3754",

publisher = "EDP Sciences",

number = "2",

}

RIS

TY - JOUR

T1 - Linear grammars with one-sided contexts and their automaton representation

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2015/4/1

Y1 - 2015/4/1

N2 - 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 Σ2-completeness of the finiteness problem for these grammars and automata.

AB - 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 Σ2-completeness of the finiteness problem for these grammars and automata.

KW - Cellular automata

KW - Conjunctive grammars

KW - Context-free grammars

KW - Contexts

KW - Trellis automata

KW - Undecidability.

UR - http://www.scopus.com/inward/record.url?scp=84936997668&partnerID=8YFLogxK

U2 - 10.1051/ita/2015004

DO - 10.1051/ita/2015004

M3 - Article

AN - SCOPUS:84936997668

VL - 49

SP - 153

EP - 158

JO - RAIRO - Theoretical Informatics and Applications

JF - RAIRO - Theoretical Informatics and Applications

SN - 0988-3754

IS - 2

ER -

ID: 41140381