Research output: Contribution to journal › Article › peer-review
Systems of equations of the form Xi=φi(X1,...,Xn) (1≤i≤n) are considered, in which the unknowns are sets of natural numbers. Expressions φi may contain the operations of union, intersection and elementwise addition S + T = {m + n {pipe} m ε S, n ε T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, 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. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.
Original language | English |
---|---|
Pages (from-to) | 319-342 |
Number of pages | 24 |
Journal | Theory of Computing Systems |
Volume | 48 |
Issue number | 2 |
DOIs | |
State | Published - 1 Jan 2011 |
ID: 41140766