Fixpoint Alternation and the Game Quantifier

J.C. Bradfield

doi:10.1007/3-540-48168-0_25

Fixpoint Alternation and the Game Quantifier

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 ∑₂⁰. 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 language	English
Title of host publication	Computer Science Logic
Subtitle of host publication	13th International Workshop, CSL’99 8th Annual Conference of the EACSL Madrid, Spain, September 20–25, 1999 Proceedings
Editors	Jörg Flum, Mario Rodriguez-Artalejo
Publisher	Springer
Pages	350-361
Number of pages	12
Volume	1683
ISBN (Electronic)	978-3-540-48168-3
ISBN (Print)	978-3-540-66536-6
DOIs	https://doi.org/10.1007/3-540-48168-0_25
Publication status	Published - 1999

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer Berlin Heidelberg
Volume	1683

Access to Document

10.1007/3-540-48168-0_25

http://dx.doi.org/10.1007/3-540-48168-0_25

Cite this

Bradfield, J. C. (1999). Fixpoint Alternation and the Game Quantifier. In J. Flum, & M. Rodriguez-Artalejo (Eds.), Computer Science Logic: 13th International Workshop, CSL’99 8th Annual Conference of the EACSL Madrid, Spain, September 20–25, 1999 Proceedings (Vol. 1683, pp. 350-361). (Lecture Notes in Computer Science; Vol. 1683). Springer. https://doi.org/10.1007/3-540-48168-0_25

@inproceedings{bb5660647eac4000a87c3265db404677,

title = "Fixpoint Alternation and the Game Quantifier",

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.",

author = "J.C. Bradfield",

year = "1999",

doi = "10.1007/3-540-48168-0_25",

language = "English",

isbn = "978-3-540-66536-6",

volume = "1683",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "350--361",

editor = "J{\"o}rg Flum and Mario Rodriguez-Artalejo",

booktitle = "Computer Science Logic",

address = "United Kingdom",

}

Bradfield, JC 1999, Fixpoint Alternation and the Game Quantifier. in J Flum & M Rodriguez-Artalejo (eds), Computer Science Logic: 13th International Workshop, CSL’99 8th Annual Conference of the EACSL Madrid, Spain, September 20–25, 1999 Proceedings. vol. 1683, Lecture Notes in Computer Science, vol. 1683, Springer, pp. 350-361. https://doi.org/10.1007/3-540-48168-0_25

Fixpoint Alternation and the Game Quantifier. / Bradfield, J.C.
Computer Science Logic: 13th International Workshop, CSL’99 8th Annual Conference of the EACSL Madrid, Spain, September 20–25, 1999 Proceedings. ed. / Jörg Flum; Mario Rodriguez-Artalejo. Vol. 1683 Springer, 1999. p. 350-361 (Lecture Notes in Computer Science; Vol. 1683).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

T1 - Fixpoint Alternation and the Game Quantifier

AU - Bradfield, J.C.

PY - 1999

Y1 - 1999

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

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

U2 - 10.1007/3-540-48168-0_25

DO - 10.1007/3-540-48168-0_25

M3 - Conference contribution

SN - 978-3-540-66536-6

VL - 1683

T3 - Lecture Notes in Computer Science

SP - 350

EP - 361

BT - Computer Science Logic

A2 - Flum, Jörg

A2 - Rodriguez-Artalejo, Mario

PB - Springer

ER -

Fixpoint Alternation and the Game Quantifier

Abstract

Publication series

Access to Document

Fingerprint

Cite this