Complexity of Equations over Sets of Natural Numbers

: Jez A, Okhotin A

Publisher: SPRINGER

: 2011

: Theory of Computing Systems

: THEORY OF COMPUTING SYSTEMS

: THEOR COMPUT SYST

: 48

: 2

: 319

: 342

: 24

: 1432-4350

DOI: https://doi.org/10.1007/s00224-009-9246-y

Systems of equations of the form X(i) = phi(i)(X(1), ..., X(n) ) (1 <= i <= n) are considered, in which the unknowns are sets of natural numbers. Expressions phi(i) may contain the operations of union, intersection and elementwise addition S + T = {m + n vertical bar m is an element of S, n is an element of 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.