# Fixpoints, games and the difference hierarchy

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 37, Issue: 1, page 1-15
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBradfield, Julian C.. "Fixpoints, games and the difference hierarchy." RAIRO - Theoretical Informatics and Applications 37.1 (2010): 1-15. <http://eudml.org/doc/92711>.

@article{Bradfield2010,

abstract = {
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 $\Sigma^0_2$. 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.
},

author = {Bradfield, Julian C.},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {Descriptive set theory; fixpoint; game quantifier; induction.; Gale-Steward games; mu-arithmetic; parity games; modal mu-calculus; arithmetic fixpoint definable sets; difference hierarchy; fixpoint hierarchy; descriptive set theory; transfinite fixpoint hierarchies},

language = {eng},

month = {3},

number = {1},

pages = {1-15},

publisher = {EDP Sciences},

title = {Fixpoints, games and the difference hierarchy},

url = {http://eudml.org/doc/92711},

volume = {37},

year = {2010},

}

TY - JOUR

AU - Bradfield, Julian C.

TI - Fixpoints, games and the difference hierarchy

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/3//

PB - EDP Sciences

VL - 37

IS - 1

SP - 1

EP - 15

AB -
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 $\Sigma^0_2$. 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.

LA - eng

KW - Descriptive set theory; fixpoint; game quantifier; induction.; Gale-Steward games; mu-arithmetic; parity games; modal mu-calculus; arithmetic fixpoint definable sets; difference hierarchy; fixpoint hierarchy; descriptive set theory; transfinite fixpoint hierarchies

UR - http://eudml.org/doc/92711

ER -

## References

top- 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. Zbl0808.03024
- J.C. Bradfield, The modal mu-calculus alternation hierarchy is strict. Theoret. Comput. Sci.195 (1997) 133-153. Zbl0915.03017
- J.C. Bradfield, Fixpoint alternation and the game quantifier, in Proc. CSL '99. Lecture Notes in Comput. Sci. 1683 (1999) 350-361. Zbl0944.03028
- J.R. Büchi, Using determinancy of games to eliminate quantifers, in Proc. FCT '77. Lecture Notes in Comput. Sci. 56 (1977) 367-378. Zbl0367.02005
- J.P. Burgess, Classical hierarchies from a modern standpoint. I. C-sets. Fund. Math.115 (1983) 81-95. Zbl0515.28002
- E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS 91 (1991).
- P.G. Hinman, The finite levels of the hierarchy of effective R-sets. Fund. Math.79 (1973) 1-10. Zbl0285.02039
- P.G. Hinman, Recursion-Theoretic Hierarchies. Springer, Berlin (1978). Zbl0371.02017
- R.S. Lubarsky, µ-definable sets of integers. J. Symb. Logic58 (1993) 291-313. Zbl0776.03022
- Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980).
- D. Niwinski, Fixed point characterization of infinite behavior of finite state systems. Theoret. Comput. Sci.189 (1997) 1-69. Zbl0893.68102
- V. Selivanov, Fine hierarchy of regular ω-languages. Theoret. Comput. Sci.191 (1998) 37-59. Zbl0908.68085

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.