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 languageEnglish
Title of host publicationDevelopments in Language Theory - 14th International Conference, DLT 2010, Proceedings
Pages291-302
Number of pages12
DOIs
StatePublished - 4 Nov 2010
Externally publishedYes
Event14th International Conference on Developments in Language Theory, DLT 2010 - London, ON, Canada
Duration: 17 Aug 201020 Aug 2010

Publication series

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

Conference

Conference14th International Conference on Developments in Language Theory, DLT 2010
Country/TerritoryCanada
CityLondon, ON
Period17/08/1020/08/10

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41142353