Deutsch
 
Benutzerhandbuch Datenschutzhinweis Impressum Kontakt
  DetailsucheBrowse

Datensatz

DATENSATZ AKTIONENEXPORT

Freigegeben

Zeitschriftenartikel

Computational Completeness of Equations Over Sets of Natural Numbers

MPG-Autoren
/persons/resource/persons79297

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

Externe Ressourcen
Es sind keine Externen Ressourcen verfügbar
Volltexte (frei zugänglich)
Es sind keine frei zugänglichen Volltexte verfügbar
Ergänzendes Material (frei zugänglich)
Es sind keine frei zugänglichen Ergänzenden Materialien verfügbar
Zitation

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.


Zitierlink: http://hdl.handle.net/11858/00-001M-0000-0024-5594-1
Zusammenfassung
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.