Fixpoints, games and the difference hierarchy

被引:7
作者
Bradfield, JC [1 ]
机构
[1] Univ Edinburgh, Sch Informat, LFCS, Edinburgh EH9 3JZ, Midlothian, Scotland
来源
RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS | 2003年 / 37卷 / 01期
关键词
descriptive set theory; fixpoint; game quantifier; induction;
D O I
10.1051/ita:2003011
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
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 Sigma(2)(0). 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.
引用
收藏
页码:1 / 15
页数:15
相关论文
共 12 条
[1]  
[Anonymous], 1978, RECURSION THEORETIC, DOI DOI 10.1007/978-3-662-12898-5
[2]  
Biichi J. R., 1977, LECTURE NOTES COMPUT, V56, P367
[3]  
Bosse U., 1993, LNCS, V702, P100
[4]   The modal mu-calculus alternation hierarchy is strict [J].
Bradfield, JC .
THEORETICAL COMPUTER SCIENCE, 1998, 195 (02) :133-153
[5]  
Bradfield JC, 1999, LECT NOTES COMPUT SC, V1683, P350
[6]   CLASSICAL HIERARCHIES FROM A MODERN STANDPOINT .1. C-SETS [J].
BURGESS, JP .
FUNDAMENTA MATHEMATICAE, 1983, 115 (02) :81-95
[7]  
EMERSON EA, 1991, P FOCS 91
[8]  
HINMAN PG, 1973, FUND MATH, V79, P1
[9]   MU-DEFINABLE SETS OF INTEGERS [J].
LUBARSKY, RS .
JOURNAL OF SYMBOLIC LOGIC, 1993, 58 (01) :291-313
[10]  
Moschovakis Yiannis N., 1980, Descriptive Set Theory