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
StatePublished - 1 Jan 2011

    Research areas

  • Computational complexity, Conjunctive grammars, Integer expressions, Language equations

    Scopus subject areas

  • Theoretical Computer Science
  • Computational Theory and Mathematics

ID: 41140766