Computational Completeness of Equations Over Sets of Natural Numbers

Jeż, Artur; Okhotin, Alexander

doi:10.1016/j.ic.2014.05.001

アイテム詳細

登録内容を編集ファイル形式で保存

一時保存へ追加

タグ情報を表示リリース履歴を表示詳細要約

公開

学術論文

Computational Completeness of Equations Over Sets of Natural Numbers

MPS-Authors

/persons/resource/persons79297

Jeż, Artur
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

External Resource

There are no locators available

Fulltext (restricted access)

There are currently no full texts shared for your IP range.

フルテキスト (公開)

公開されているフルテキストはありません

付随資料 (公開)

There is no public supplementary material available

引用

Jeż, A., & Okhotin, A. (2014). Computational Completeness of Equations Over Sets of Natural Numbers. Information and Computation, 237, 56-94. doi:10.1016/j.ic.2014.05.001.

引用: https://hdl.handle.net/11858/00-001M-0000-0024-5594-1

要旨

Systems of finitely many equations of the form φ(X_1, …, X_n)=ψ(X_1, …, X_n) are considered, in which the unknowns X_i are sets of natural numbers, while the expressions φ,ψ may contain singleton constants and the operations of union 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. The same results are established for equations with addition and intersection.