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 language | English |
---|---|
Title of host publication | Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
Publisher | IBFI Schloss Dagstuhl |
Pages | 373-384 |
Number of pages | 12 |
ISBN (Print) | 9783939897064 |
State | Published - 2008 |
Externally published | Yes |
Event | 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 - Bordeaux, France Duration: 21 Feb 2008 → 23 Feb 2008 |
Name | Proceedings of the 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
---|
Conference | 25th International Symposium on Theoretical Aspects of Computer Science, STACS 2008 |
---|---|
Country/Territory | France |
City | Bordeaux |
Period | 21/02/08 → 23/02/08 |
ID: 78926693