de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Journal Article

Computational Completeness of Equations Over Sets of Natural Numbers

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons79297

Jeż,  Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Jeż, A., & Okhotin, A. (2014). Computational Completeness of Equations Over Sets of Natural Numbers. Information and Computation, 237, 56-94. doi:10.1016/j.ic.2014.05.001.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0024-5594-1
Abstract
Systems of finitely many equations of the form φ(X_1, …, X_n)=ψ(X_1, …, X_n) are considered, in which the unknowns X_i 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.