Fixpoint Alternation and the Game Quantifier

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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 ∑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.
Original languageEnglish
Title of host publicationComputer Science Logic
Subtitle of host publication13th International Workshop, CSL’99 8th Annual Conference of the EACSL Madrid, Spain, September 20–25, 1999 Proceedings
EditorsJörg Flum, Mario Rodriguez-Artalejo
PublisherSpringer Berlin Heidelberg
Pages350-361
Number of pages12
Volume1683
ISBN (Electronic)978-3-540-48168-3
ISBN (Print)978-3-540-66536-6
DOIs
Publication statusPublished - 1999

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume1683

Fingerprint Dive into the research topics of 'Fixpoint Alternation and the Game Quantifier'. Together they form a unique fingerprint.

Cite this