On the Computational Completeness of Equations over Sets of Natural Numbers
On the Computational Completeness of Equations over Sets of Natural Numbers
复制标题
论自然数集方程的计算完备性
DOI：
10.1007/978-3-540-70583-3_6
复制
发表时间：
2008
影响因子：
1.3
通讯作者：
A. Okhotin
中科院分区：
文献类型：
--
作者：
Artur Jeż;A. Okhotin
形式为 φ j (X 1 , ..., X n ) = i3/4 的方程组？考虑 j (X 1 , ..., X n ) 和 $1 \leqslant j \leqslant m$，其中未知数 X i 是自然数集，而表达式 φ j ,i¾? j 可以包含单例常量以及并集（可能被交集代替）和成对加法运算。结果表明，由此类系统的唯一（最小、最大）解表示的集合族正是递归（分别为 r.e，co-r.e）数集的族。这些系统的基本决策问题位于算术层次结构中。
Systems of equations of the form φ j (X 1 , ..., X n ) = i¾? 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 ,i¾? 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.