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 = {m + n | 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|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.

Original languageEnglish
Title of host publicationSTACS 2010 - 27th International Symposium on Theoretical Aspects of Computer Science
Pages477-488
Number of pages12
DOIs
StatePublished - 2010
Event27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010 - Nancy, France
Duration: 4 Mar 20106 Mar 2010

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume5
ISSN (Print)1868-8969

Conference

Conference27th International Symposium on Theoretical Aspects of Computer Science, STACS 2010
Country/TerritoryFrance
CityNancy
Period4/03/106/03/10

    Scopus subject areas

  • Software

    Research areas

  • Arithmetical hierarchy, Computability, Hyper-arithmetical hierarchy, Language equations

ID: 78935862