It has recently been shown that several computational models - trellis automata, recursive functions and Turing machines - admit characterization by resolved systems of language equations with different sets of language-theoretic operations. This paper investigates how simple the systems of equations from the computationally universal types could be while still retaining their universality. It is shown that resolved systems with two variables and two equations are as expressive as more complicated systems, while one-variable equations are "almost" as expressive. Additionally, language equations with added quotient with regular languages are shown to be able to denote every arithmetical set.
| Original language | English |
|---|---|
| Title of host publication | Machines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers |
| Editors | Maurice Margenstern |
| Pages | 292-303 |
| Number of pages | 12 |
| Volume | 3354 |
| DOIs | |
| State | Published - 2005 |
| Externally published | Yes |
| Event | 4th International Conference on Machines, Computations, and Universality, MCU 2004 - Saint Petersburg, Russian Federation Duration: 21 Sep 2004 → 24 Sep 2004 |
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer Nature |
| ISSN (Print) | 0302-9743 |
| Conference | 4th International Conference on Machines, Computations, and Universality, MCU 2004 |
|---|---|
| Country/Territory | Russian Federation |
| City | Saint Petersburg |
| Period | 21/09/04 → 24/09/04 |
ID: 78926142