Advertisement
Published in:
2008 | OriginalPaper | Chapter
On the Computational Completeness of Equations over Sets of Natural Numbers
Authors : Artur Jeż, Alexander Okhotin
Published in: Automata, Languages and Programming
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Systems of equations of the form
ϕ
j
(
X
1
, ...,
X
n
) =
ψ
j
(
X
1
, ...,
X
n
) with
$1 \leqslant j \leqslant m$
are considered, in which the unknowns
X
i
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
. 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.