TY - GEN

T1 - On the computational completeness of equations over sets of natural numbers

AU - Jez, Artur

AU - Okhotin, Alexander

PY - 2008/8/14

Y1 - 2008/8/14

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=49049100916&partnerID=8YFLogxK

U2 - 10.1007/978-3-540-70583-3_6

DO - 10.1007/978-3-540-70583-3_6

M3 - Conference contribution

AN - SCOPUS:49049100916

SN - 3540705821

SN - 9783540705826

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 63

EP - 74

BT - Automata, Languages and Programming - 35th International Colloquium, ICALP 2008, Proceedings

T2 - 35th International Colloquium on Automata, Languages and Programming, ICALP 2008

Y2 - 7 July 2008 through 11 July 2008

ER -