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 languageEnglish
Title of host publicationMachines, Computations, and Universality, 4th International Conference, MCU 2004, Saint Petersburg, Russia, September 21-24, 2004, Revised Selected Papers
EditorsMaurice Margenstern
Pages292-303
Number of pages12
Volume3354
DOIs
StatePublished - 2005
Externally publishedYes
Event4th International Conference on Machines, Computations, and Universality, MCU 2004 - Saint Petersburg, Russian Federation
Duration: 21 Sep 200424 Sep 2004

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Nature
ISSN (Print)0302-9743

Conference

Conference4th International Conference on Machines, Computations, and Universality, MCU 2004
Country/TerritoryRussian Federation
CitySaint Petersburg
Period21/09/0424/09/04

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78926142