2026-07-21T20:30:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:2478 2024-03-06T10:33:25Z ddc:004 open_access

On Equations over Sets of Integers Jez, Artur Okhotin, Alexander Language equations computability arithmetical hierarchy hyper-arithmetical hierarchy Systems of equations with sets of integers as unknowns are considered. It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets. Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Artur Jez and Alexander Okhotin 2010 Is Part Of LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2010.2478 urn:nbn:de:0030-drops-24780 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478 eng https://creativecommons.org/licenses/by-nd/3.0/legalcode