<div dir="ltr"><br><div class="gmail_quote"><div dir="ltr"><span style="font-size:14px;border-collapse:collapse"><span style="border-collapse:collapse"><div class="gmail_quote"><span style="border-collapse:collapse"><div style="padding:12px 0px 3px"><span style="font-size:small"><font color="#000000"><span>Kobe</span></font></span><span style="font-size:small"><font color="#000000"> </font></span><span style="font-size:small"><font color="#000000"><span>Colloquium</span></font></span><span style="font-size:small"><font color="#000000"> on <span>Logic</span>, Statistics and Informatics </font></span><br></div><div style="direction:ltr;margin:5px 15px 0px 0px;padding-bottom:5px"><div dir="ltr"><span style="border-collapse:collapse"><span style="border-collapse:collapse"><div><span style="font-size:small"><font color="#000000"><br></font></span></div><div><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000">以下の要領で</font></span><span style="font-size:small"><font color="#000000">コロキウム</font></span><span style="font-size:small"><font color="#000000">を開催します。</font></span></span></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000"><br></font></span></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000">日時：</font></span></span></font><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000">2015年7月14日（火）</font></span></span><span style="font-size:small"><font color="#000000">13:30-15:00</font></span></div></span></span><span style="border-collapse:collapse"><span style="border-collapse:collapse"><div style="display:inline!important"><span style="font-size:small"><font color="#000000"></font></span><font face="arial, sans-serif"><span style="border-collapse:collapse"><div style="display:inline!important"><span style="font-size:small"><font color="#000000">講演者：Olivier Finkel （パリ第７大学）</font></span></div></span></font></div></span></span><span style="border-collapse:collapse"><span style="border-collapse:collapse"><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000">場所：神戸大学自然科学総合研究棟3号館4階421室（プレゼンテーション室）</font></span></span></font></div><div><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000"><br></font></span></span></font></div></span></span><div><span style="font-size:small"><font color="#000000">============================================================</font></span></div><span style="border-collapse:collapse"><span style="border-collapse:collapse"><font face="arial, sans-serif"><span style="border-collapse:collapse"><span style="font-size:small"><font color="#000000"><br></font></span></span></font></span></span><span style="border-collapse:collapse"><span style="border-collapse:collapse"><font face="arial, sans-serif"><span style="font-size:small"><font color="#000000"><span style="border-collapse:collapse"></span></font></span></font></span></span></div></div></span><span style="font-size:small"><font color="#000000">題目： </font></span></div></span>Logic, Complexity and Infinite Computations<br></span><div style="font-size:14px"><span style="border-collapse:collapse"><font face="arial, sans-serif"><span style="border-collapse:collapse"><font color="#000000"><font color="#222222"><br></font></font></span></font><span style="border-collapse:collapse"><div class="gmail_quote"><font color="#000000">アブストラクト：</font></div></span><span style="border-collapse:collapse;background-color:rgb(255,255,255)"><div class="gmail_quote"><span style="color:rgb(0,0,0);font-family:Times;font-size:medium;line-height:16px;text-align:justify">The theory of automata reading infinite words, which is closely related to infinite games, is a rich theory which is used for the specification and verification of non-terminating systems. </span></div><span style="color:rgb(0,0,0);font-family:Times;font-size:medium;line-height:16px;text-align:justify">We prove that the Wadge hierarchy of omega-languages accepted by 1-counter Büchi automata (or by 2-tape Büchi automata) is equal to the Wadge hierarchy of omega-languages accepted by Büchi Turing machines, which forms the class of effective analytic sets. </span><br style="color:rgb(0,0,0);font-family:Times;line-height:16px;text-align:justify"><span style="color:rgb(0,0,0);font-family:Times;font-size:medium;line-height:16px;text-align:justify">Moreover the topological complexity of an omega-language accepted by a 1-counter Büchi automaton, or of an infinitary rational relation accepted by a 2-tape Büchi automaton, is not determined by the axiomatic system ZFC. In particular, there is a 1-counter Büchi automaton A (respectively, a 2-tape Büchi automaton B) and two models V1 and V2 of ZFC such that the omega-language L(A) (respectively, the infinitary rational relation L(B)) is Borel in V1 but not in V2. </span><br style="color:rgb(0,0,0);font-family:Times;line-height:16px;text-align:justify"><span style="color:rgb(0,0,0);font-family:Times;font-size:medium;line-height:16px;text-align:justify">We prove that the determinacy of Gale-Stewart games whose winning sets are accepted by real-time 1-counter Büchi automata (or by 2-tape Büchi automata) is equivalent to the determinacy of (effective) analytic Gale-Stewart games which is known to be a large cardinal assumption. Using some results of set theory we prove that one can effectively construct a 1-counter Büchi automaton (respectively, a 2-tape Büchi automaton) A such that: (1) There exists a model of ZFC in which Player 1 has a winning strategy in the Gale-Stewart game G(L(A)); but the winning strategies cannot be recursive and not even hyperarithmetical. (2) There exists a model of ZFC in which the Gale-Stewart game is not determined. </span><br style="color:rgb(0,0,0);font-family:Times;line-height:16px;text-align:justify"><span style="color:rgb(0,0,0);font-family:Times;font-size:medium;line-height:16px;text-align:justify">We also prove that the determinacy of Wadge games between two players in charge of omega-languages accepted by real-time 1-counter Büchi automata (or by 2-tape Büchi automata) is equivalent to the effective analytic determinacy, and thus is not provable in ZFC.</span></span></span></div><div><div style="text-align:justify"><font color="#000000" face="Times" size="3"><span style="line-height:16px;background-color:rgb(249,247,228)"><br></span></font></div><span style="font-size:14px;border-collapse:collapse"><span style="border-collapse:collapse"><div class="gmail_quote"><span style="border-collapse:collapse"><div><div><font color="#000000">========================================================</font></div><div><font color="#000000"><br></font></div></div><div><font color="#000000">交通：阪急六甲駅またはJR六甲道駅から神戸市バス36系統「鶴甲団地」<br>行きに乗車，「神大本部工学部前」停留所下車，徒歩すぐ．<br></font><a href="http://www.kobe-u.ac.jp/info/access/rokko/rokkodai-dai2.htm" target="_blank"><font color="#000000">http://www.</font><font color="#000000"><span>kobe</span></font><font color="#000000">-u.ac.jp/info/access/rokko/rokkodai-dai2.htm</font></a></div></span></div></span></span></div></div>
</div><br></div>