TY - JOUR

T1 - Complexity of Equations over Sets of Natural Numbers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2011/1/1

Y1 - 2011/1/1

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Conjunctive grammars

KW - Integer expressions

KW - Language equations

UR - http://www.scopus.com/inward/record.url?scp=80051665679&partnerID=8YFLogxK

U2 - 10.1007/s00224-009-9246-y

DO - 10.1007/s00224-009-9246-y

M3 - Article

AN - SCOPUS:80051665679

VL - 48

SP - 319

EP - 342

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -