A1 Refereed original research article in a scientific journal
Complexity of Equations over Sets of Natural Numbers
Authors: Jez A, Okhotin A
Publisher: SPRINGER
Publication year: 2011
Journal: Theory of Computing Systems
Journal name in source: THEORY OF COMPUTING SYSTEMS
Journal acronym: THEOR COMPUT SYST
Volume: 48
Issue: 2
First page : 319
Last page: 342
Number of pages: 24
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-009-9246-y(external)
Abstract
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.
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.
UTU Research Portal