Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › Рецензирование
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.
| Язык оригинала | английский |
|---|---|
| Название основной публикации | Developments in Language Theory - 17th International Conference, DLT 2013, Proceedings |
| Страницы | 277-288 |
| Число страниц | 12 |
| DOI | |
| Состояние | Опубликовано - 19 сен 2013 |
| Событие | 17th International Conference on Developments in Language Theory, DLT 2013 - Marne-la-Vallee, Франция Продолжительность: 18 июн 2013 → 21 июн 2013 |
| Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Том | 7907 LNCS |
| ISSN (печатное издание) | 0302-9743 |
| ISSN (электронное издание) | 1611-3349 |
| конференция | 17th International Conference on Developments in Language Theory, DLT 2013 |
|---|---|
| Страна/Tерритория | Франция |
| Город | Marne-la-Vallee |
| Период | 18/06/13 → 21/06/13 |
ID: 41143545