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.

References

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,

1984.

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,

2007.

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