Standard

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

LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Nature, 2014. p. 190-201 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review

Harvard

Barash, M & Okhotin, A 2014, Linear grammars with one-sided contexts and their automaton representation. in LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8392 LNCS, Springer Nature, pp. 190-201, 11th Latin American Theoretical Informatics Symposium, LATIN 2014, Montevideo, Uruguay, 31/03/14. https://doi.org/10.1007/978-3-642-54423-1_17

APA

Barash, M., & Okhotin, A. (2014). Linear grammars with one-sided contexts and their automaton representation. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings (pp. 190-201). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8392 LNCS). Springer Nature. https://doi.org/10.1007/978-3-642-54423-1_17

Vancouver

Barash M, Okhotin A. Linear grammars with one-sided contexts and their automaton representation. In LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Nature. 2014. p. 190-201. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-54423-1_17

Author

Barash, Mikhail ; Okhotin, Alexander. / Linear grammars with one-sided contexts and their automaton representation. LATIN 2014: Theoretical Informatics - 11th Latin American Symposium, Proceedings. Springer Nature, 2014. pp. 190-201 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@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",

}

RIS

TY - GEN

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

AU - Barash, Mikhail

AU - Okhotin, Alexander

PY - 2014/1/1

Y1 - 2014/1/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 σ02-completeness of the finiteness problem for these grammars.

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

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

U2 - 10.1007/978-3-642-54423-1_17

DO - 10.1007/978-3-642-54423-1_17

M3 - Conference contribution

AN - SCOPUS:84899932589

SN - 9783642544224

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 190

EP - 201

BT - LATIN 2014

PB - Springer Nature

T2 - 11th Latin American Theoretical Informatics Symposium, LATIN 2014

Y2 - 31 March 2014 through 4 April 2014

ER -

ID: 41478686