A1 Refereed original research article in a scientific journal
Least and greatest solutions of equations over sets of integers
Authors: Jez A, Okhotin A
Publisher: ELSEVIER SCIENCE BV
Publication year: 2016
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 619
First page : 68
Last page: 86
Number of pages: 19
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2016.01.013
Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, S + T = {m + n vertical bar m is an element of S, n is an element of T}. These equations were recently studied by the authors ("Representing hyper-arithmetical sets by equations over sets of integers", Theory of Computing Systems, 51 (2012), 196-228), and it was shown that the class of sets representable by their unique solutions is exactly the class of hyper-arithmetical sets. In this paper it is demonstrated that greatest solutions of such equations represent exactly the Sigma(1)(1)-sets in the analytical hierarchy, and all those sets can already be represented by systems in the resolved form X-i = phi(i)(X-1, ... , X-n). Least solutions of such resolved systems represent exactly the recursively enumerable sets. (C) 2016 Elsevier B.V. All rights reserved.