Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2003__37_1_1_0,
author = {Bradfield, Julian C.},
title = {Fixpoints, games and the difference hierarchy},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {1--15},
publisher = {EDP-Sciences},
volume = {37},
number = {1},
year = {2003},
doi = {10.1051/ita:2003011},
mrnumber = {1991748},
zbl = {1043.03038},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita:2003011/}
}
TY - JOUR AU - Bradfield, Julian C. TI - Fixpoints, games and the difference hierarchy JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2003 SP - 1 EP - 15 VL - 37 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita:2003011/ DO - 10.1051/ita:2003011 LA - en ID - ITA_2003__37_1_1_0 ER -
%0 Journal Article %A Bradfield, Julian C. %T Fixpoints, games and the difference hierarchy %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2003 %P 1-15 %V 37 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita:2003011/ %R 10.1051/ita:2003011 %G en %F ITA_2003__37_1_1_0
Bradfield, Julian C. Fixpoints, games and the difference hierarchy. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 37 (2003) no. 1, pp. 1-15. doi: 10.1051/ita:2003011
Cité par Sources :