کد مقاله کد نشریه سال انتشار مقاله انگلیسی ترجمه فارسی نسخه تمام متن
4661574 1344844 2016 29 صفحه PDF ندارد دانلود رایگان
عنوان انگلیسی مقاله
Infinite games specified by 2-tape automata
ترجمه فارسی عنوان
بازی های بی نهایت مشخص شده توسط اتوماتای نوار 2
کلمات کلیدی
زبان اتوماتیک و رسمی ، منطق در علوم کامپیوتر؛ بازی گیل استوارت؛ اتوماتای BUCHI نوار 2 ؛ اتوماتای شمارنده 1 ؛ معین؛ معین تحلیلی موثر؛ مدل های تئوری مجموعه؛ هم استقلال
03E60; 03E35; 03B70; 68Q45; 03D05; 68Q15; 68Q17; 03E15Automata and formal languages; Logic in computer science; Gale–Stewart games; 2-tape Büchi automaton; 1-counter automaton; Determinacy; Effective analytic determinacy; Models of set theory; Independenc
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات منطق ریاضی
چکیده انگلیسی

We prove that the determinacy of Gale–Stewart games whose winning sets are infinitary rational relations accepted 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. Then we prove that winning strategies, when they exist, can be very complex, i.e. highly non-effective, in these games. We prove the same results for Gale–Stewart games with winning sets accepted by real-time 1-counter Büchi automata, then extending previous results obtained about these games.1.There exists a 2-tape Büchi automaton (respectively, a real-time 1-counter Büchi automaton) AA such that: (a) there is a model of ZFC in which Player 1 has a winning strategy σ   in the game G(L(A))G(L(A)) but σ   cannot be recursive and not even in the class (Σ21∪Π21); (b) there is a model of ZFC in which the game G(L(A))G(L(A)) is not determined.2.There exists a 2-tape Büchi automaton (respectively, a real-time 1-counter Büchi automaton) AA such that L(A)L(A) is an arithmetical Δ30-set and Player 2 has a winning strategy in the game G(L(A))G(L(A)) but has no hyperarithmetical winning strategies in this game.3.There exists a recursive sequence of 2-tape Büchi automata (respectively, of real-time 1-counter Büchi automata) AnAn, n≥1n≥1, such that all games G(L(An))G(L(An)) are determined, but for which it is Π21-complete hence highly undecidable to determine whether Player 1 has a winning strategy in the game G(L(An))G(L(An)). Then we consider the strengths of determinacy for these games, and we prove the following results.1.There exists a 2-tape Büchi automaton (respectively, a real-time 1-counter Büchi automaton) A♯A♯ such that the game G(A♯)G(A♯) is determined iff the effective analytic determinacy holds.2.There is a transfinite sequence of 2-tape Büchi automata (respectively, of real-time 1-counter Büchi automata) (Aα)α<ω1CK, indexed by recursive ordinals, such that the games G(L(Aα))G(L(Aα)) have strictly increasing strengths of determinacy. We also show that the determinacy of Wadge games between two players in charge of infinitary rational relations accepted by 2-tape Büchi automata is equivalent to the (effective) analytic Wadge determinacy and thus also equivalent to the (effective) analytic determinacy.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Annals of Pure and Applied Logic - Volume 167, Issue 12, December 2016, Pages 1184–1212
نویسندگان
,