Результаты исследований: Публикации в книгах, отчётах, сборниках, трудах конференций › статья в сборнике материалов конференции › научная › Рецензирование
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.
Язык оригинала | английский |
---|---|
Название основной публикации | 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 июл 2008 → 11 июл 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/08 → 11/07/08 |
ID: 41143826