Equations over sets of integers with addition only

: Jez A, Okhotin A

Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE

: 2016

: Journal of Computer and System Sciences

: JOURNAL OF COMPUTER AND SYSTEM SCIENCES

: J COMPUT SYST SCI

: 82

: 6

: 1007

: 1019

: 13

: 0022-0000

: 1090-2724

DOI: https://doi.org/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 subset of N there exists a system with a unique (least, greatest) solution containing a component T with S = {n vertical bar 16n + 13 is an element of T}. Testing solution existence for these equations is Pi(0)(1)-complete, solution uniqueness is Pi(0)(2)-complete, and finiteness of the set of solutions is Sigma(0-)(3)complete. A similar construction for integers represents any hyper-arithmetical set S subset of Z by a set T subset of Z satisfying S = {n vertical bar 16n is an element of T }, whereas testing solution existence is Sigma(1)(1)-complete. (C) 2016 Elsevier Inc. All rights reserved.