License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2008.1319
URN: urn:nbn:de:0030-drops-13194
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2008/1319/
Go to the corresponding LIPIcs Volume Portal

Okhotin, Alexander ; Jez, Artur

Complexity of solutions of equations over sets of natural numbers

pdf-format:
22011.OkhotinAlexander.Paper.1319.pdf (0.2 MB)

Abstract

Systems of equations over sets of natural numbers (or,
equivalently, language equations over a one-letter alphabet) of the
form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant
n$) are considered. Expressions $varphi_i$ may contain the
operations of union, intersection and pairwise sum $A plus B = {x
+ y mid x in A, y in B$. A system with an EXPTIME-complete
least solution is constructed, and it is established that least
solutions of all such systems are in EXPTIME. The general
membership problem for these equations is proved to be
EXPTIME-complete.


BibTeX - Entry

@InProceedings{okhotin_et_al:LIPIcs:2008:1319,
  author =	{Alexander Okhotin and Artur Jez},
  title =	{{Complexity of solutions of equations  over sets of natural numbers}},
  booktitle =	{25th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{373--384},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-06-4},
  ISSN =	{1868-8969},
  year =	{2008},
  volume =	{1},
  editor =	{Susanne Albers and Pascal Weil},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2008/1319},
  URN =		{urn:nbn:de:0030-drops-13194},
  doi =		{10.4230/LIPIcs.STACS.2008.1319},
  annote =	{Keywords: }
}

Collection: 25th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2008
Date of publication: 06.02.2008

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI