Standard

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

в: RAIRO - Theoretical Informatics and Applications, Том 49, № 2, 01.04.2015, стр. 153-158.

Результаты исследований: Научные публикации в периодических изданиях › статья › Рецензирование

Harvard

Barash, M & Okhotin, A 2015, 'Linear grammars with one-sided contexts and their automaton representation', RAIRO - Theoretical Informatics and Applications, Том. 49, № 2, стр. 153-158. https://doi.org/10.1051/ita/2015004

APA

Barash, M., & Okhotin, A. (2015). Linear grammars with one-sided contexts and their automaton representation. RAIRO - Theoretical Informatics and Applications, 49(2), 153-158. https://doi.org/10.1051/ita/2015004

Vancouver

Barash M, Okhotin A. Linear grammars with one-sided contexts and their automaton representation. RAIRO - Theoretical Informatics and Applications. 2015 Апр. 1;49(2):153-158. https://doi.org/10.1051/ita/2015004

Author

Barash, Mikhail ; Okhotin, Alexander. / Linear grammars with one-sided contexts and their automaton representation. в: RAIRO - Theoretical Informatics and Applications. 2015 ; Том 49, № 2. стр. 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