It is shown that the recently discovered computational universality in systems of language equations over a unary alphabet occurs already in systems of the simplest form, with one unknown X and two equations XXK∈=∈XXL and XM∈=∈N, where K, L, M, N∈ ∈a * are four regular constants. Every recursive (r.e., co-r.e.) set can be encoded in a unique (least, greatest) solution of a system of such a form. The proofs are carried out in terms of equations over sets of numbers.
Original language | English |
---|---|
Title of host publication | Developments in Language Theory - 14th International Conference, DLT 2010, Proceedings |
Pages | 291-302 |
Number of pages | 12 |
DOIs | |
State | Published - 4 Nov 2010 |
Externally published | Yes |
Event | 14th International Conference on Developments in Language Theory, DLT 2010 - London, ON, Canada Duration: 17 Aug 2010 → 20 Aug 2010 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Volume | 6224 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 14th International Conference on Developments in Language Theory, DLT 2010 |
---|---|
Country/Territory | Canada |
City | London, ON |
Period | 17/08/10 → 20/08/10 |
ID: 41142353