×

The determinacy strength of pushdown \(\omega\)-languages. (English) Zbl 1420.03089

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
PDFBibTeX XMLCite
Full Text: DOI