Informatics Report Series


Report   

EDI-INF-RR-0556


Related Pages

Report (by Number) Index
Report (by Date) Index
Author Index
Institute Index

Home
Title:Fixpoints, games and the difference hierarchy
Authors: Julian Bradfield
Date: 2003
Publication Title:Theoretical Informatics and Applications
Publisher:EDP Sciences
Publication Type:Journal Article Publication Status:Published
Volume No:37(1) Page Nos:1-16
DOI:10.1051/ita:2003011
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},
}


Home : Publications : Report 

Please mail <reports@inf.ed.ac.uk> with any changes or corrections.
Unless explicitly stated otherwise, all material is copyright The University of Edinburgh