Computational Completeness of Equations Over Sets of Natural Numbers

Jeż, Artur; Okhotin, Alexander

doi:10.1016/j.ic.2014.05.001

Item

ITEM ACTIONSEXPORT

Add to Basket

Local TagsRelease HistoryDetailsSummary

Released

Journal Article

Computational Completeness of Equations Over Sets of Natural Numbers

MPS-Authors

/persons/resource/persons79297

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

External Resource

No external resources are shared

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

Fulltext (public)

There are no public fulltexts stored in PuRe

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: https://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.