A1 Refereed original research article in a scientific journal
Equations over sets of integers with addition only
Authors: Jez A, Okhotin A
Publisher: ACADEMIC PRESS INC ELSEVIER SCIENCE
Publication year: 2016
Journal: Journal of Computer and System Sciences
Journal name in source: JOURNAL OF COMPUTER AND SYSTEM SCIENCES
Journal acronym: J COMPUT SYST SCI
Volume: 82
Issue: 6
First page : 1007
Last page: 1019
Number of pages: 13
ISSN: 0022-0000
eISSN: 1090-2724
DOI: https://doi.org/10.1016/j.jcss.2016.02.003
Abstract
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.
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.
UTU Research Portal