Least and greatest solutions of equations over sets of integers

详细信息    查看全文

• 作者：Artur Jeż^a ; ¹ ; ^{aje@cs.uni.wroc.pl" class="auth_mail" title="E-mail the corresponding author} ; Alexander Okhotin^b ; ² ; ^{alexander.okhotin@utu.fi" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Language equations ; Computability ; Analytical hierarchy
• 刊名：Theoretical Computer Science
• 出版年：2016
• 出版时间：14 March 2016
• 年：2016
• 卷：619
• 期：Complete
• 页码：68-86
• 全文大小：566 K

文摘

Systems of equations with sets of integers as unknowns are considered, with the operations of union, intersection and addition of sets, class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000244&_mathId=si1.gif&_user=111111111&_pii=S0304397516000244&_rdoc=1&_issn=03043975&md5=6d3a9f00d630bf7cc6b18308638d7ce5">class="imgLazyJSB inlineImage" height="13" width="183" alt="View the MathML source" style="margin-top: -5px; vertical-align: middle" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397516000244-si1.gif">class="mathContainer hidden">class="mathCode">$S+T=\{m+n|m\in S,n\in 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 class="mathmlsrc">title="View the MathML source" class="mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000244&_mathId=si137.gif&_user=111111111&_pii=S0304397516000244&_rdoc=1&_issn=03043975&md5=295ca64a2c4293044c7241695b30e4f1">class="imgLazyJSB inlineImage" height="18" width="17" alt="View the MathML source" title="View the MathML source" src="/sd/grey_pxl.gif" data-inlimgeid="1-s2.0-S0304397516000244-si137.gif">class="mathContainer hidden">class="mathCode">${\mathrm{\Sigma }}_1^1$-sets in the analytical hierarchy, and all those sets can already be represented by systems in the resolved form  class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0304397516000244&_mathId=si253.gif&_user=111111111&_pii=S0304397516000244&_rdoc=1&_issn=03043975&md5=58f05ced0f1070b3bbbfc765fc670301" title="Click to view the MathML source">X_i=φ_i(X₁,…,X_n)class="mathContainer hidden">class="mathCode">$X_i={\phi }_i(X_1,\dots ,X_n)$. Least solutions of such resolved systems represent exactly the recursively enumerable sets.