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 language | English |
---|---|
Title of host publication | Computer Science - Theory and Applications - Second International Symposium on Computer Science in Russia, CSR 2007, Proceedings |
Publisher | Springer Nature |
Pages | 168-181 |
Number of pages | 14 |
ISBN (Print) | 9783540745099 |
DOIs | |
State | Published - 2007 |
Externally published | Yes |
Event | 2nd International Symposium on Computer Science in Russia, CSR 2007 - Ekaterinburg, Russian Federation Duration: 3 Sep 2007 → 7 Sep 2007 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 4649 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 2nd International Symposium on Computer Science in Russia, CSR 2007 |
---|---|
Country/Territory | Russian Federation |
City | Ekaterinburg |
Period | 3/09/07 → 7/09/07 |
ID: 78926459