Computational completeness of equations over sets of natural numbers

Research output

8 Citations (Scopus)

Abstract

Systems of finitely many equations of the form φ( X1,..., Xn)=ψ(X1,...,Xn) are considered, in which the unknowns Xi are sets of natural numbers, while the expressions φ,ψ may contain singleton constants and the operations of union and pairwise addition S+T={m+n|m S,n T}. It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy. The same results are established for equations with addition and intersection.

Original languageEnglish
Pages (from-to)56-94
Number of pages39
JournalInformation and Computation
Volume237
DOIs
Publication statusPublished - 1 Jan 2014

Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Computer Science Applications
  • Computational Theory and Mathematics

Fingerprint Dive into the research topics of 'Computational completeness of equations over sets of natural numbers'. Together they form a unique fingerprint.

Cite this