TY - JOUR

T1 - Representing Hyper-arithmetical Sets by Equations over Sets of Integers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2012/8/1

Y1 - 2012/8/1

N2 - 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, defined as S + T={m +n {pipe} m ∈ S,n ∈ 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 - T = {m - n {pipe} m ∈ S, n ∈ T, m ≥ n}. Testing whether a given system has a solution is Σ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.

AB - 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, defined as S + T={m +n {pipe} m ∈ S,n ∈ 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 - T = {m - n {pipe} m ∈ S, n ∈ T, m ≥ n}. Testing whether a given system has a solution is Σ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.

KW - Arithmetical hierarchy

KW - Computability

KW - Hyper-arithmetical hierarchy

KW - Language equations

UR - http://www.scopus.com/inward/record.url?scp=84861234622&partnerID=8YFLogxK

U2 - 10.1007/s00224-011-9352-5

DO - 10.1007/s00224-011-9352-5

M3 - Article

AN - SCOPUS:84861234622

VL - 51

SP - 196

EP - 228

JO - Theory of Computing Systems

JF - Theory of Computing Systems

SN - 1432-4350

IS - 2

ER -