A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Complexity of Equations over Sets of Natural Numbers
Tekijät: Jez A, Okhotin A
Kustantaja: SPRINGER
Julkaisuvuosi: 2011
Journal: Theory of Computing Systems
Tietokannassa oleva lehden nimi: THEORY OF COMPUTING SYSTEMS
Lehden akronyymi: THEOR COMPUT SYST
Vuosikerta: 48
Numero: 2
Aloitussivu: 319
Lopetussivu: 342
Sivujen määrä: 24
ISSN: 1432-4350
DOI: https://doi.org/10.1007/s00224-009-9246-y
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali