Fixpoints, games and the difference hierarchy

Research output: Contribution to journalArticlepeer-review

Abstract / Description of output

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 ∑20. 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.
Original languageEnglish
Pages (from-to)1-15
Number of pages15
JournalRAIRO: Theoretical Informatics and Applications
Issue number1
Publication statusPublished - 1 Jan 2003

Keywords / Materials (for Non-textual outputs)

  • Descriptive set theory
  • fixpoint
  • game quantifier
  • induction


Dive into the research topics of 'Fixpoints, games and the difference hierarchy'. Together they form a unique fingerprint.

Cite this