Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik GmbH scholarly article en Jez, Artur; Okhotin, Alexander http://www.dagstuhl.de/lipics License
when quoting this document, please refer to the following
DOI:
URN: urn:nbn:de:0030-drops-24780
URL:

;

On Equations over Sets of Integers

pdf-format:


Abstract

Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.

BibTeX - Entry

@InProceedings{jez_et_al:LIPIcs:2010:2478,
  author =	{Artur Jez and Alexander Okhotin},
  title =	{{On Equations over Sets of Integers}},
  booktitle =	{27th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{477--488},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-16-3},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{5},
  editor =	{Jean-Yves Marion and Thomas Schwentick},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2010/2478},
  URN =		{urn:nbn:de:0030-drops-24780},
  doi =		{http://dx.doi.org/10.4230/LIPIcs.STACS.2010.2478},
  annote =	{Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy}
}

Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy
Seminar: 27th International Symposium on Theoretical Aspects of Computer Science
Issue date: 2010
Date of publication: 2010


DROPS-Home | Fulltext Search | Imprint Published by LZI