Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
Unambiguous conjunctive grammars over a one-letter alphabet. / Jez, Artur; Okhotin, Alexander.
Developments in Language Theory - 17th International Conference, DLT 2013, Proceedings. 2013. стр. 277-288 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Том 7907 LNCS).Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
}
TY - GEN
T1 - Unambiguous conjunctive grammars over a one-letter alphabet
AU - Jez, Artur
AU - Okhotin, Alexander
PY - 2013/9/19
Y1 - 2013/9/19
N2 - It is demonstrated that unambiguous conjunctive grammars over a unary alphabet ∑ = {a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base k ≥ 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits {⌊k+9/4⌋,..., ⌊k+1/2⌋}, the language of all strings an with the base-k notation of the form 1 w 1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable.
AB - It is demonstrated that unambiguous conjunctive grammars over a unary alphabet ∑ = {a} have non-trivial expressive power, and that their basic properties are undecidable. The key result is that for every base k ≥ 11 and for every one-way real-time cellular automaton operating over the alphabet of base-k digits {⌊k+9/4⌋,..., ⌊k+1/2⌋}, the language of all strings an with the base-k notation of the form 1 w 1, where w is accepted by the automaton, is generated by an unambiguous conjunctive grammar. Another encoding is used to simulate a cellular automaton in a unary language containing almost all strings. These constructions are used to show that for every fixed unambiguous conjunctive language L0, testing whether a given unambiguous conjunctive grammar generates L0 is undecidable.
UR - http://www.scopus.com/inward/record.url?scp=84880697852&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-38771-5_25
DO - 10.1007/978-3-642-38771-5_25
M3 - Conference contribution
AN - SCOPUS:84880697852
SN - 9783642387708
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 277
EP - 288
BT - Developments in Language Theory - 17th International Conference, DLT 2013, Proceedings
T2 - 17th International Conference on Developments in Language Theory, DLT 2013
Y2 - 18 June 2013 through 21 June 2013
ER -
ID: 41143545