Game Development Reference
In-Depth Information
Exercise 4.8
Adapt the proof of Theorem 4.20 to get a proof of Theo-
rem 4.36.
A. Arnold. The mu-calculus alternation-depth is strict on binary trees. RAIRO
Informatique Theorique et Applications , 33:329-339, 1999.
J. Bradfield. The modal μ -calculus alternation hierarchy is strict. Theoretical
Computer Science , 195:133-153, 1998.
A. Chandra and D. Harel. Structure and complexity for relational queries. Journal
of Computer and System Sciences , 25:99-128, 1982.
E. Dahlhaus. Skolem normal forms concerning the least fixed point. In E. Borger, ed-
itor, Computation Theory and Logic , number 270 in Lecture Notes in Computer
Science, pages 101-106. Springer Verlag, 1987.
A. Dawar and E. Gradel. The descriptive complexity of parity games. In Proceedings
of 22th Annual Conference of the European Association for Computer Science
Logic CSL 2008 , pages 354-368, 2008.
A. Dawar, E. Gradel, and S. Kreutzer. Inflationary fixed points in modal logic.
ACM Transactions on Computational Logic , 5:282 - 315, 2004.
A. Dawar, E. Gradel, and S. Kreutzer. Backtracking games and inflationary fixed
points. Theoretical Computer Science , 350:174-187, 2006.
W. F. Dowling and J. H. Gallier. Linear-time algorithms for testing the satisfiability
of propositional horn formulae. Journal of Logic Programming , 1(3):267-284,
S. Dziembowski. Bounded-variable fixpoint queries are PSPACE-complete. In
10th Annual Conference on Computer Science Logic CSL 96. Selected papers ,
Lecture Notes in Computer Science Nr. 1258, pages 89-105. Springer, 1996.
H.-D. Ebbinghaus and J. Flum. Finite Model Theory . Springer, 2nd edition, 1999.
A. Emerson and C. Jutla. Tree automata, mu-calculus and determinacy. In Proc.
32nd IEEE Symp. on Foundations of Computer Science , pages 368-377, 1991.
D. Fischer, E. Gradel, and L. Kaiser. Model checking games for the quantitative
μ -calculus. Theory of Computing Systems , 2009.
E. Gradel. Finite Model Theory and Descriptive Complexity. In Finite Model
Theory and Its Applications . Springer-Verlag, 2007.
E. Gradel and I. Walukiewicz. Positional determinacy of games with infinitely many
priorities. Logical Methods in Computer Science , 2006.
E. Gradel, P. G. Kolaitis, L. Libkin, M. Marx, J. Spencer, M. Y. Vardi, Y. Venema,
and S.Weinstein. Finite Model Theory and Its Applications . Springer, Berlin,
R. Greenlaw, J. Hoover, and W. Ruzzo. Limits to Parallel Computation. P-
Completeness Theory . Oxford University Press, Oxford, 1995.
N. Immerman. Relational queries computable in polynomial time. Information and
Control , 68:86-104, 1986.
A. Itai and J. Makowsky. Unification as a complexity measure for logic programming.
Journal of Logic Programming , 4:105-117, 1987.
M. Jurdzinski. Small progress measures for solving parity games. In Proceedings of
17th Annual Symposium on Theoretical Aspects of Computer Science, STACS
Search Nedrilad ::

Custom Search