Geodesic
The determinacy strength of pushdown ω-languages
Li, Wenjuan 1   ; Tanaka, Kazuyuki 1
1 Mathematical Institute, Tohoku University, 6-3, Aramaki Aza-Aoba, Aoba-ku, Sendai 980-8578, Japan.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 29-50 Cet article a éte moissonné depuis la source Numdam

Voir la notice de l'article

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 ω-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.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2017006
Classification : 03D05, 03B30, 68Q45
Keywords: Gale–Stewart games, pushdown ω-languages, 2-stack visibly pushdown automata, reverse mathematics

Li, Wenjuan  1   ; Tanaka, Kazuyuki  1

1 Mathematical Institute, Tohoku University, 6-3, Aramaki Aza-Aoba, Aoba-ku, Sendai 980-8578, Japan. 
@article{ITA_2017__51_1_29_0,
     author = {Li, Wenjuan and Tanaka, Kazuyuki},
     title = {The determinacy strength of pushdown $\omega{}$-languages},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {29--50},
     year = {2017},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {1},
     doi = {10.1051/ita/2017006},
     mrnumber = {3678028},
     zbl = {1420.03089},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2017006/}
}
TY  - JOUR
AU  - Li, Wenjuan
AU  - Tanaka, Kazuyuki
TI  - The determinacy strength of pushdown $\omega{}$-languages
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 29
EP  - 50
VL  - 51
IS  - 1
PB  - EDP-Sciences
UR  - http://geodesic.mathdoc.fr/articles/10.1051/ita/2017006/
DO  - 10.1051/ita/2017006
LA  - en
ID  - ITA_2017__51_1_29_0
ER  - 
%0 Journal Article
%A Li, Wenjuan
%A Tanaka, Kazuyuki
%T The determinacy strength of pushdown $\omega{}$-languages
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 29-50
%V 51
%N 1
%I EDP-Sciences
%U http://geodesic.mathdoc.fr/articles/10.1051/ita/2017006/
%R 10.1051/ita/2017006
%G en
%F ITA_2017__51_1_29_0
Li, Wenjuan; Tanaka, Kazuyuki. The determinacy strength of pushdown $\omega{}$-languages. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 51 (2017) no. 1, pp. 29-50. doi: 10.1051/ita/2017006

Cité par Sources :