DOI

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 сен 20077 сен 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/077/09/07

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 78926459