Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Research › peer-review
Systems of equations of the form φj(X1,...,X n)=ψj(X1,...,Xn) with 1 ≤ j ≤ m are considered, in which the unknowns Xi are sets of natural numbers, while the expressions φj,ψj may contain singleton constants and the operations of union (possibly replaced by intersection) and pairwise addition S + T = {m + n| m ∈ S, n ∈ T}. It is shown that the family of sets representable by unique (least, greatest) solutions of such systems is exactly the family of recursive (r.e., co-r.e., respectively) sets of numbers. Basic decision problems for these systems are located in the arithmetical hierarchy.
Original language | English |
---|---|
Title of host publication | Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings |
Pages | 63-74 |
Number of pages | 12 |
Edition | PART 2 |
DOIs | |
State | Published - 14 Aug 2008 |
Event | 35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland Duration: 7 Jul 2008 → 11 Jul 2008 |
Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Number | PART 2 |
Volume | 5126 LNCS |
ISSN (Print) | 0302-9743 |
ISSN (Electronic) | 1611-3349 |
Conference | 35th International Colloquium on Automata, Languages and Programming, ICALP 2008 |
---|---|
Country/Territory | Iceland |
City | Reykjavik |
Period | 7/07/08 → 11/07/08 |
ID: 41143826