Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, S + T = {m + n | m ∈ S, n ∈ T}. These equations were recently studied by the authors ("On equations over sets of integers", STACS 2010), and it was shown that their unique solutions represent exactly the Σ1 1 hyperarithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the sets in the analytical hierarchy, and these sets can already be represented by systems in the resolved form Xi = φi (X1, ..., X n). Least solutions of such resolved systems represent exactly the recursively enumerable sets.

Original languageEnglish
Title of host publicationMathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings
Pages441-452
Number of pages12
DOIs
StatePublished - 2010
Externally publishedYes
Event35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010 - Brno, Czech Republic
Duration: 23 Aug 201027 Aug 2010

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6281 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010
Country/TerritoryCzech Republic
CityBrno
Period23/08/1027/08/10

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 78945579