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.

Original languageEnglish
Title of host publicationComputer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings
PublisherSpringer Nature
Pages168-181
Number of pages14
ISBN (Print)9783540745099
DOIs
StatePublished - 2007
Externally publishedYes
Event2nd International Symposium on Computer Science in Russia, CSR 2007 - Ekaterinburg, Russian Federation
Duration: 3 Sep 20077 Sep 2007

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume4649 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference2nd International Symposium on Computer Science in Russia, CSR 2007
Country/TerritoryRussian Federation
CityEkaterinburg
Period3/09/077/09/07

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78926459