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 language | English |
|---|---|
| Title of host publication | Mathematical Foundations of Computer Science 2010 - 35th International Symposium, MFCS 2010, Proceedings |
| Pages | 441-452 |
| Number of pages | 12 |
| DOIs | |
| State | Published - 2010 |
| Externally published | Yes |
| Event | 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010 - Brno, Czech Republic Duration: 23 Aug 2010 → 27 Aug 2010 |
| Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
|---|---|
| Volume | 6281 LNCS |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
| Conference | 35th International Symposium on Mathematical Foundations of Computer Science, MFCS 2010 |
|---|---|
| Country/Territory | Czech Republic |
| City | Brno |
| Period | 23/08/10 → 27/08/10 |
ID: 78945579