Standard

One-nonterminal conjunctive grammars over a unary alphabet. / Jez, Artur; Okhotin, Alexander.

Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. 2009. стр. 191-202 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 5675 LNCS).

Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование

Harvard

Jez, A & Okhotin, A 2009, One-nonterminal conjunctive grammars over a unary alphabet. в Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Том. 5675 LNCS, стр. 191-202, 4th International Computer Science Symposium in Russia, CSR 2009, Novosibirsk, Российская Федерация, 18/08/09. https://doi.org/10.1007/978-3-642-03351-3_19

APA

Jez, A., & Okhotin, A. (2009). One-nonterminal conjunctive grammars over a unary alphabet. в Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings (стр. 191-202). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 5675 LNCS). https://doi.org/10.1007/978-3-642-03351-3_19

Vancouver

Jez A, Okhotin A. One-nonterminal conjunctive grammars over a unary alphabet. в Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. 2009. стр. 191-202. (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-03351-3_19

Author

Jez, Artur ; Okhotin, Alexander. / One-nonterminal conjunctive grammars over a unary alphabet. Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings. 2009. стр. 191-202 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

BibTeX

@inproceedings{d08931b3fb6f43498aedd6c50e3c90ef,
title = "One-nonterminal conjunctive grammars over a unary alphabet",
abstract = "Conjunctive grammars over an alphabet ∑ = {a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X = φ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.",
author = "Artur Jez and Alexander Okhotin",
year = "2009",
doi = "10.1007/978-3-642-03351-3_19",
language = "English",
isbn = "3642033504",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "191--202",
booktitle = "Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings",
note = "4th International Computer Science Symposium in Russia, CSR 2009 ; Conference date: 18-08-2009 Through 23-08-2009",

}

RIS

TY - GEN

T1 - One-nonterminal conjunctive grammars over a unary alphabet

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2009

Y1 - 2009

N2 - Conjunctive grammars over an alphabet ∑ = {a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X = φ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.

AB - Conjunctive grammars over an alphabet ∑ = {a} are studied, with the focus on the special case with a unique nonterminal symbol. Such a grammar is equivalent to an equation X = φ(X) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple nonterminals can be encoded into a grammar with a single nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-nonterminal conjunctive grammars over {a} is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.

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

U2 - 10.1007/978-3-642-03351-3_19

DO - 10.1007/978-3-642-03351-3_19

M3 - Conference contribution

AN - SCOPUS:70350303842

SN - 3642033504

SN - 9783642033506

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

SP - 191

EP - 202

BT - Computer Science - Theory and Applications - 4th International Computer Science Symposium in Russia, CSR 2009, Proceedings

T2 - 4th International Computer Science Symposium in Russia, CSR 2009

Y2 - 18 August 2009 through 23 August 2009

ER -

ID: 78935797