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 φjj 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 languageEnglish
Title of host publicationAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Pages63-74
Number of pages12
EditionPART 2
DOIs
StatePublished - 14 Aug 2008
Event35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Iceland
Duration: 7 Jul 200811 Jul 2008

Publication series

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

Conference

Conference35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Country/TerritoryIceland
CityReykjavik
Period7/07/0811/07/08

    Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

ID: 41143826