Fixpoints, games and the difference hierarchy

Julian C. Bradfield

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2003)

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

Abstract

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

How to cite

top

Bradfield, Julian C.. "Fixpoints, games and the difference hierarchy." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 37.1 (2003): 1-15. <http://eudml.org/doc/245025>.

@article{Bradfield2003,
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 - Informatique Théorique et 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; transfinite fixpoint hierarchies},
language = {eng},
number = {1},
pages = {1-15},
publisher = {EDP-Sciences},
title = {Fixpoints, games and the difference hierarchy},
url = {http://eudml.org/doc/245025},
volume = {37},
year = {2003},
}

TY - JOUR
AU - Bradfield, Julian C.
TI - Fixpoints, games and the difference hierarchy
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2003
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; transfinite fixpoint hierarchies
UR - http://eudml.org/doc/245025
ER -

References

top
  1. [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. Zbl0808.03024
  2. [2] J.C. Bradfield, The modal mu-calculus alternation hierarchy is strict. Theoret. Comput. Sci. 195 (1997) 133-153. Zbl0915.03017MR1609327
  3. [3] J.C. Bradfield, Fixpoint alternation and the game quantifier, in Proc. CSL ’99. Lecture Notes in Comput. Sci. 1683 (1999) 350-361. Zbl0944.03028
  4. [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. Zbl0367.02005
  5. [5] J.P. Burgess, Classical hierarchies from a modern standpoint. I. C -sets. Fund. Math. 115 (1983) 81-95. Zbl0515.28002MR699874
  6. [6] E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS 91 (1991). 
  7. [7] P.G. Hinman, The finite levels of the hierarchy of effective R -sets. Fund. Math. 79 (1973) 1-10. Zbl0285.02039MR389565
  8. [8] P.G. Hinman, Recursion-Theoretic Hierarchies. Springer, Berlin (1978). Zbl0371.02017MR499205
  9. [9] R.S. Lubarsky, μ -definable sets of integers. J. Symb. Logic 58 (1993) 291-313. Zbl0776.03022MR1217190
  10. [10] Y.N. Moschovakis, Descriptive Set Theory. North-Holland, Amsterdam (1980). Zbl0433.03025MR561709
  11. [11] D. Niwiński, Fixed point characterization of infinite behavior of finite state systems. Theoret. Comput. Sci. 189 (1997) 1-69. Zbl0893.68102MR1483617
  12. [12] V. Selivanov, Fine hierarchy of regular ω -languages. Theoret. Comput. Sci. 191 (1998) 37-59. Zbl0908.68085MR1490562

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.