Systems of equations over sets of natural numbers (or, equivalently, language equations over a one-letter alphabet) of the form Xi = φi(X1,...,Xn) (1 ≤ i ≤ n) are considered. Expressions φi may contain the operations of union, intersection and pairwise sum A+B = {x+y | x ∈ A, y ∈ 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.

Original languageEnglish
Title of host publicationProceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
PublisherIBFI Schloss Dagstuhl
Pages373-384
Number of pages12
ISBN (Print)9783939897064
StatePublished - 2008
Externally publishedYes
Event25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 - Bordeaux, France
Duration: 21 Feb 200823 Feb 2008

Publication series

NameProceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008

Conference

Conference25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008
Country/TerritoryFrance
CityBordeaux
Period21/02/0823/02/08

    Scopus subject areas

  • Computer Science(all)

ID: 78926693