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 -