A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä
Least and greatest solutions of equations over sets of integers
Tekijät: Jez A, Okhotin A
Kustantaja: ELSEVIER SCIENCE BV
Julkaisuvuosi: 2016
Journal: Theoretical Computer Science
Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE
Lehden akronyymi: THEOR COMPUT SCI
Vuosikerta: 619
Aloitussivu: 68
Lopetussivu: 86
Sivujen määrä: 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.