References

1. Krzysztof Apt & Erich Grädel (2011): Lectures in Game Theory for Computer Scientists. Cambridge University Press, doi:10.1017/CBO9780511973468.
2. Dietmar Berwanger, Anuj Dawar, Paul Hunter, Stephan Kreutzer & Jan Obdržálek: The DAG-Width of Directed Graphs, doi:10.1016/j.jctb.2012.04.004. To appear.
3. Dietmar Berwanger & Erich Grädel (2005): Entanglement – A Measure for the Complexity of Directed Graphs with Applications to Logic and Games. In: Proceedings of LPAR 2004, Montevideo, Uruguay, LNCS 3452. Springer, pp. 209–223, doi:10.1007/978-3-540-32275-7_15.
4. Dietmar Berwanger, Erich Grädel, Łukasz Kaiser & Roman Rabinovich: Entanglement and the Complexity of Directed Graphs. Theoretical Computer Science. Available at http://logic.rwth-aachen.de/~rabinovich/entangle.pdf. To appear.
5. Bruno Courcelle, Joost Engelfriet & Grzegorz Rozenberg (1993): Handle-Rewriting Hypergraph Grammars. J. Comput. Syst. Sci. 46(2), pp. 218–270, doi:10.1016/0022-0000(93)90004-G.
6. John Fearnley (2010): Non-oblivious Strategy Improvement. In: Edmund M. Clarke & Andrei Voronkov: LPAR (Dakar), LNCS 6355. Springer, pp. 212–230, doi:10.1007/978-3-642-17511-4_13.
7. Oliver Friedmann: A Subexponential Lower Bound for Policy Iteration Based on Snare Memorization. Available at http://files.oliverfriedmann.de/papers/fearnley_lower_bound.pdf. Submitted for publication.
8. Oliver Friedmann: A Subexponential Lower Bound for the Least Recently Considered Rule for Solving Linear Programs and Games. Available at http://files.oliverfriedmann.de/papers/least_recently_considered_lower_bound.pdf. Submitted for publication.
9. Oliver Friedmann (2011): Exponential Lower Bounds for Solving Infinitary Payoff Games and Linear Programs. Ludwig-Maximilians-University Munich. Available at http://edoc.ub.uni-muenchen.de/13294.
10. P. Hunter & S. Kreutzer (2008): Digraph Measures: Kelly Decompositions, Games, and Orderings. Theor. Comput. Sci. 399(3), pp. 206–219, doi:10.1016/j.tcs.2008.02.038.
11. Marcin Jurdziński (1998): Deciding the Winner in Parity Games is in UP co-UP. Inf. Process. Lett. 68(3), pp. 119–124, doi:10.1016/S0020-0190(98)00150-1.
12. Marcin Jurdziński (2000): Small Progress Measures for Solving Parity Games. In: Horst Reichel & Sophie Tison: STACS, LNCS 1770. Springer, pp. 290–301, doi:10.1007/3-540-46541-3 _24.
13. Marcin Jurdziński, Mike Paterson & Uri Zwick (2006): A Deterministic Subexponential Algorithm for Solving Parity Games. In: SODA. ACM Press, pp. 117–123, doi:10.1145/1109557.1109571. Available at http://dl.acm.org/citation.cfm?id=1109557.
14. Marcin Jurdziński & Jens Vöge (2000): A Discrete Strategy Improvement Algorithm for Solving Parity Games (Extended Abstract). In: E. A. Emerson & A. P. Sistla: Computer Aided Verification, 12th International Conference, CAV 2000, Proceedings, LBCS 1855. Springer, Chicago, IL, USA, pp. 202–215, doi:10.1007/10722167_18.
15. Jan Obdržálek (2003): Fast Mu-Calculus Model Checking when Tree-Width Is Bounded. In: Warren A. Hunt Jr. & Fabio Somenzi: CAV, LNCS 2725. Springer, pp. 80–92, doi:10.1007/978-3-540-45069-6_7.
16. Jan Obdržálek (2007): Clique-Width and Parity Games. In: J. Duparc & T. A. Henzinger: CSL '07, LNCS 4646. Springer, pp. 54–68, doi:10.1007/978-3-540-74915-8-8.
17. Sven Schewe (2008): An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games. In: Michael Kaminski & Simone Martini: CSL, LNCS 5213. Springer, pp. 369–384, doi:10.1007/978-3-540-87531-4_27.

Comments and questions to: eptcs@eptcs.org

For website issues: webmaster@eptcs.org