Equations over sets of integers with addition only

• Published in: Journal of computer and system sciences 2016-09, Vol.82 (6), p.1007-1019
• Main Authors: Jeż, Artur, Okhotin, Alexander
• Format: Article
• Language: English
• Subjects: Computability; Concatenation; Constants; Equivalence; Integers; Language equations; Mathematical analysis; Mathematical models; Recursive; Unary languages; Uniqueness
• ISSN: 0022-0000; 1090-2724
• DOI: 10.1016/j.jcss.2016.02.003

Systems of equations of the form X=Y+Z and X=C are considered, in which the unknowns are sets of integers, the plus operator denotes element-wise sum of sets, and C is an ultimately periodic constant. For natural numbers, such equations are equivalent to language equations over a one-symbol alphabet using concatenation and regular constants. It is shown that such systems are computationally universal: for every recursive (r.e., co-r.e.) set S⊆N there exists a system with a unique (least, greatest) solution containing a component T with S={n|16n+13∈T}. Testing solution existence for these equations is Π10-complete, solution uniqueness is Π20-complete, and finiteness of the set of solutions is Σ30-complete. A similar construction for integers represents any hyper-arithmetical set S⊆Z by a set T⊆Z satisfying S={n|16n∈T}, whereas testing solution existence is Σ11-complete. •Investigating equations with sets of natural numbers (or any integers) as unknowns.•The only operation is element-wise addition of sets.•For natural numbers, these equations are computationally universal.•For integers, any hyper-arithmetical set can be encoded in a solution.•Solution existence, uniqueness, etc., are undecidable.