- 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 $\Delta^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.
- Links To Paper
- 1st Link
- Bibtex format
- @Article{EDI-INF-RR-0556,
- author = {
Julian Bradfield
},
- title = {Fixpoints, games and the difference hierarchy},
- journal = {Theoretical Informatics and Applications},
- publisher = {EDP Sciences},
- year = 2003,
- volume = {37(1)},
- pages = {1-16},
- doi = {10.1051/ita:2003011},
- url = {http://www.edpsciences.org/articles/ita/pdf/2003/01/ita0303.pdf},
- }
|