• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On Language Equations XXK=XXL and XM=N Over a Unary Alphabet

Tommi Lehtinen, Alexander Okhotin, On Language Equations XXK=XXL and XM=N Over a Unary Alphabet. In: 2010.

Abstract:

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 \subseteq 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.

BibTeX entry:

@INPROCEEDINGS{pLeOk10a,
  title = {On Language Equations XXK=XXL and XM=N Over a Unary Alphabet},
  author = {Lehtinen, Tommi and Okhotin, Alexander},
  year = {2010},
  keywords = {Language equations, unary languages, computability},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication