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

On Equations over Sets of Numbers and their Limitations

Tommi Lehtinen, Alexander Okhotin, On Equations over Sets of Numbers and their Limitations. In: Developments in Language Theory 2009, LNCS, 360-371, Springer, 2009.

Abstract:

Systems of equations of the form
X=Y+Z and X=C,
in which the unknowns are sets of natural numbers,
``+'' denotes
elementwise sum of sets S+T={m+n | m \in S, n \in T},
and C is an ultimately periodic constant,
have recently been proved to be computationally universal
(Je\.z, Okhotin, ``Equations over sets of natural numbers with addition only'', STACS 2009).
This paper establishes some limitations of such systems.
A class of sets of numbers
that cannot be represented
by unique, least or greatest solutions of systems of this form
is defined,
and a particular set in this class is constructed.

BibTeX entry:

@INPROCEEDINGS{inpLeOk09a,
  title = {On Equations over Sets of Numbers and their Limitations},
  booktitle = {Developments in Language Theory 2009},
  author = {Lehtinen, Tommi and Okhotin, Alexander},
  volume = {LNCS},
  number = {5583},
  publisher = {Springer},
  pages = {360-371},
  year = {2009},
  keywords = {Language equations, Computational universality},
}

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

Edit publication