Li, Wenjuan; Tanaka, Kazuyuki The determinacy strength of pushdown \(\omega\)-languages. (English) Zbl 1420.03089 RAIRO, Theor. Inform. Appl. 51, No. 1, 29-50 (2017). Summary: We investigate the determinacy strength of infinite games whose winning sets are recognized by nondeterministic pushdown automata with various acceptance conditions, e.g., safety, reachability and co-Büchi conditions. In terms of the foundational program “Reverse Mathematics”, the determinacy strength of such games is measured by the complexity of a winning strategy required by the determinacy. Infinite games recognized by nondeterministic pushdown automata have some resemblance to those by deterministic 2-stack visibly pushdown automata with the same acceptance conditions. So, we first investigate the determinacy of games recognized by deterministic 2-stack visibly pushdown automata, together with that by nondeterministic ones. Then, for instance, we prove that the determinacy of games recognized by pushdown automata with a reachability condition is equivalent to the weak König lemma, stating that every infinite binary tree has an infinite path. While the determinacy for pushdown \(\omega\)-languages with a Büchi condition is known to be independent from ZFC, we here show that for the co-Büchi condition, the determinacy is exactly captured by ATR\(_0\), another popular system of reverse mathematics asserting the existence of a transfinite hierarchy produced by iterating arithmetical comprehension along a given well-order. Finally, we conclude that all results for pushdown automata in this paper indeed hold for 1-counter automata. MSC: 03D05 Automata and formal grammars in connection with logical questions 03B30 Foundations of classical theories (including reverse mathematics) 68Q45 Formal languages and automata Keywords:Gale-Stewart games; pushdown \(\omega\)-languages; 2-stack visibly pushdown automata; reverse mathematics PDFBibTeX XMLCite \textit{W. Li} and \textit{K. Tanaka}, RAIRO, Theor. Inform. Appl. 51, No. 1, 29--50 (2017; Zbl 1420.03089) Full Text: DOI