| Issue |
RAIRO-Theor. Inf. Appl.
Volume 37, Number 1, January/March 2003
|
|
|---|---|---|
| Page(s) | 1 - 15 | |
| DOI | https://doi.org/10.1051/ita:2003011 | |
| Published online | 15 November 2003 | |
Fixpoints, games and the difference hierarchy
LFCS, School of Informatics,
University of Edinburgh, Edinburgh, EH9 3JZ, UK; jcb@inf.ed.ac.uk.
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 
. 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.
Mathematics Subject Classification: 03E15 / 68Q45
Key words: Descriptive set theory / fixpoint / game quantifier / induction.
© EDP Sciences, 2003
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.