Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings |
Издатель | Springer Nature |
Страницы | 168-181 |
Число страниц | 14 |
ISBN (печатное издание) | 9783540745099 |
DOI | |
Состояние | Опубликовано - 2007 |
Опубликовано для внешнего пользования | Да |
Событие | 2nd International Symposium on Computer Science in Russia, CSR 2007 - Ekaterinburg, Российская Федерация Продолжительность: 3 сен 2007 → 7 сен 2007 |
Название | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Том | 4649 LNCS |
ISSN (печатное издание) | 0302-9743 |
ISSN (электронное издание) | 1611-3349 |
конференция | 2nd International Symposium on Computer Science in Russia, CSR 2007 |
---|---|
Страна/Tерритория | Российская Федерация |
Город | Ekaterinburg |
Период | 3/09/07 → 7/09/07 |
ID: 78926459