کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
435378 | 689900 | 2016 | 19 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Least and greatest solutions of equations over sets of integers Least and greatest solutions of equations over sets of integers](/preview/png/435378.png)
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|m∈S,n∈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 Σ11-sets in the analytical hierarchy, and all those sets can already be represented by systems in the resolved form Xi=φi(X1,…,Xn)Xi=φi(X1,…,Xn). Least solutions of such resolved systems represent exactly the recursively enumerable sets.
Journal: Theoretical Computer Science - Volume 619, 14 March 2016, Pages 68–86