Standard

Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. / Jez, Artur; Okhotin, Alexander.

Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. Springer Nature, 2007. p. 168-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4649 LNCS).

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

Harvard

Jez, A & Okhotin, A 2007, Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. in Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 4649 LNCS, Springer Nature, pp. 168-181, 2nd International Symposium on Computer Science in Russia, CSR 2007, Ekaterinburg, Russian Federation, 3/09/07. https://doi.org/10.1007/978-3-540-74510-5_19

APA

Jez, A., & Okhotin, A. (2007). Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. In Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings (pp. 168-181). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 4649 LNCS). Springer Nature. https://doi.org/10.1007/978-3-540-74510-5_19

Vancouver

Jez A, Okhotin A. Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. In Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. Springer Nature. 2007. p. 168-181. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-540-74510-5_19

Author

Jez, Artur ; Okhotin, Alexander. / Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings. Springer Nature, 2007. pp. 168-181 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{b3bd4e1cbaf5426e8db83f425c0d7fcc,
title = "Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth",
abstract = "It has recently been proved (Je{\.z}, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.",
author = "Artur Jez and Alexander Okhotin",
year = "2007",
doi = "10.1007/978-3-540-74510-5_19",
language = "English",
isbn = "9783540745099",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Nature",
pages = "168--181",
booktitle = "Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings",
address = "Germany",
note = "2nd International Symposium on Computer Science in Russia, CSR 2007 ; Conference date: 03-09-2007 Through 07-09-2007",

}

RIS

TY - GEN

T1 - Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2007

Y1 - 2007

N2 - It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.

AB - It has recently been proved (Jeż, DLT 2007) that conjunctive grammars (that is, context-free grammars augmented by conjunction) generate some nonregular languages over a one-letter alphabet. The present paper improves this result by constructing conjunctive grammars for a larger class of unary languages. The results imply undecidability of a number of decision problems of unary conjunctive grammars, as well as nonexistence of an r.e. bound on the growth rate of generated languages. An essential step of the argument is a simulation of a cellular automaton recognizing positional notation of numbers using language equations.

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

U2 - 10.1007/978-3-540-74510-5_19

DO - 10.1007/978-3-540-74510-5_19

M3 - Conference contribution

AN - SCOPUS:37249047954

SN - 9783540745099

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

SP - 168

EP - 181

BT - Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings

PB - Springer Nature

T2 - 2nd International Symposium on Computer Science in Russia, CSR 2007

Y2 - 3 September 2007 through 7 September 2007

ER -

ID: 78926459