DOI

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.

Язык оригиналаанглийский
Название основной публикацииAutomata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings
Страницы63-74
Число страниц12
ИзданиеPART 2
DOI
СостояниеОпубликовано - 14 авг 2008
Событие35th International Colloquium on Automata, Languages and Programming, ICALP 2008 - Reykjavik, Исландия
Продолжительность: 7 июл 200811 июл 2008

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
НомерPART 2
Том5126 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция35th International Colloquium on Automata, Languages and Programming, ICALP 2008
Страна/TерриторияИсландия
ГородReykjavik
Период7/07/0811/07/08

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 41143826