Fixpoints, games and the difference hierarchy
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 1-15.

Drawing on an analogy with temporal fixpoint logic, we relate the arithmetic fixpoint definable sets to the winning positions of certain games, namely games whose winning conditions lie in the difference hierarchy over Σ 2 0 . This both provides a simple characterization of the fixpoint hierarchy, and refines existing results on the power of the game quantifier in descriptive set theory. We raise the problem of transfinite fixpoint hierarchies.

DOI : https://doi.org/10.1051/ita:2003011
Classification : 03E15,  68Q45
Mots clés : descriptive set theory, fixpoint, game quantifier, induction
@article{ITA_2003__37_1_1_0,
     author = {Bradfield, Julian C.},
     title = {Fixpoints, games and the difference hierarchy},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {1--15},
     publisher = {EDP-Sciences},
     volume = {37},
     number = {1},
     year = {2003},
     doi = {10.1051/ita:2003011},
     zbl = {1043.03038},
     mrnumber = {1991748},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2003011/}
}
Bradfield, Julian C. Fixpoints, games and the difference hierarchy. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 1-15. doi : 10.1051/ita:2003011. http://www.numdam.org/articles/10.1051/ita:2003011/

[1] U. Bosse, An “Ehrenfeucht-Fraïssé game” for fixpoint logic and stratified fixpoint logic, in Computer science logic. San Miniato, Lecture Notes in Comput. Sci. 702 (1992) 100-114. | Zbl 0808.03024

[2] J.C. Bradfield, The modal mu-calculus alternation hierarchy is strict. Theoret. Comput. Sci. 195 (1997) 133-153. | MR 1609327 | Zbl 0915.03017

[3] J.C. Bradfield, Fixpoint alternation and the game quantifier, in Proc. CSL '99. Lecture Notes in Comput. Sci. 1683 (1999) 350-361. | Zbl 0944.03028

[4] J.R. Büchi, Using determinancy of games to eliminate quantifers, in Proc. FCT '77. Lecture Notes in Comput. Sci. 56 (1977) 367-378. | Zbl 0367.02005

[5] J.P. Burgess, Classical hierarchies from a modern standpoint 115 (1983) 81-95. | MR 699874 | Zbl 0515.28002

[6] E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS 91 (1991).

[7] P.G. Hinman, The finite levels of the hierarchy of effective R-sets. Fund. Math. 79 (1973) 1-10. | MR 389565 | Zbl 0285.02039

[8] P.G. Hinman, Recursion-Theoretic Hierarchies. Springer, Berlin (1978). | MR 499205 | Zbl 0371.02017

[9] R.S. Lubarsky, μ-definable sets of integers. J. Symb. Logic 58 (1993) 291-313. | MR 1217190 | Zbl 0776.03022

[10] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). | MR 561709 | Zbl 0433.03025

[11] D. Niwiński, Fixed point characterization of infinite behavior of finite state systems. Theoret. Comput. Sci. 189 (1997) 1-69. | MR 1483617 | Zbl 0893.68102

[12] V. Selivanov, Fine hierarchy of regular ω-languages. Theoret. Comput. Sci. 191 (1998) 37-59. | MR 1490562 | Zbl 0908.68085