22 Citations (Scopus)

Abstract

Systems of equations of the form Xii(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.

Original languageEnglish
Pages (from-to)319-342
Number of pages24
JournalTheory of Computing Systems
Volume48
Issue number2
DOIs
Publication statusPublished - 1 Jan 2011

Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Complexity of Equations over Sets of Natural Numbers'. Together they form a unique fingerprint.

Cite this