References

  1. A. Arnold, A. Vincent & I. Walukiewicz (2003): Games for synthesis of controllers with partial observation. Theor. Comput. Sci. 303(1), pp. 7–34, doi:10.1016/S0304-3975(02)00442-5.
  2. H. Björklund & S. G. Vorobyov (2005): Combinatorial structure and randomized subexponential algorithms for infinite games. Theor. Comput. Sci 349(3), pp. 347–360, doi:10.1016/j.tcs.2005.07.041.
  3. A. Browne, E. M. Clarke, S. Jha, D. E. Long & W. Marrero (1997): An improved algorithm for the evaluation of fixpoint expressions. TCS 178(1–2), pp. 237–255, doi:10.1016/S0304-3975(96)00228-9.
  4. J. R. Burch, E. M. Clarke, K. L. McMillan, D. L. Dill & L. J. Hwang (1992): Symbolic Model Checking: 10^20 States and Beyond. Information and Computation 98(2), pp. 142–170, doi:10.1016/0890-5401(92)90017-A.
  5. E. A. Emerson & C. S. Jutla (1991): Tree Automata, μ-Calculus and Determinacy. In: Proc. 32nd Symp. on Foundations of Computer Science. IEEE, San Juan, Puerto Rico, pp. 368–377, doi:10.1109/SFCS.1991.185392.
  6. O. Friedmann (2009): An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it. In: Proc. 24th Ann. IEEE Symp. on Logic in Computer Science, LICS'09. IEEE, pp. 145–156, doi:10.1109/LICS.2009.27.
  7. O. Friedmann (2011): Recursive algorithm for parity games requires exponential time. RAIRO - Theor. Inf. and Applic. 45(4), pp. 449–457. Available at http://dx.doi.org/10.1051/ita/2011124.
  8. O. Friedmann & M. Lange (2009): Solving Parity Games in Practice. In: Proc. 7th Int. Symp. on Automated Technology for Verification and Analysis, ATVA'09, LNCS 5799, pp. 182–196, doi:10.1007/978-3-642-04761-9_15.
  9. O. Friedmann & M. Lange (2012): Two Local Strategy Improvement Schemes for Parity Game Solving. Journal of Foundations of Computer Science 23(3), pp. 669–685, doi:10.1142/S0129054112400333.
  10. O. Friedmann, M. Latte & M. Lange (2013): Satisfiability Games for Branching-Time Logics. Logical Methods in Computer Science 9(4), doi:10.2168/LMCS-9(4:5)2013.
  11. K. Heljanko, M. Keinänen, M. Lange & I. Niemelä (2012): Solving Parity Games by a Reduction to SAT. Journal of Computer and System Sciences 78, pp. 430–440, doi:10.1016/j.jcss.2011.05.004.
  12. M. Jurdziński (1998): Deciding the winner in parity games is in UPco-UP. Inf. Process. Lett. 68(3), pp. 119–124, doi:10.1016/S0020-0190(98)00150-1.
  13. M. Jurdziński (2000): Small progress measures for solving parity games. In: H. Reichel & S. Tison: Proc. 17th Ann. Symp. on Theoretical Aspects of Computer Science, STACS'00, LNCS 1770. Springer, pp. 290–301, doi:10.1007/3-540-46541-3_24.
  14. M. Jurdzinski, M. Paterson & U. Zwick (2008): A Deterministic Subexponential Algorithm for Solving Parity Games. SIAM J. Comput 38(4), pp. 1519–1532. Available at http://dx.doi.org/10.1137/070686652.
  15. D. A. Martin (1975): Borel determinacy. The annals of Mathematics 102(2), pp. 363–371, doi:10.2307/1971035.
  16. S. Schewe (2007): Solving Parity Games in Big Steps. In: Proc. 27th Int. Conf. on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'07, LNCS 4855. Springer, pp. 449–460, doi:10.1007/978-3-540-77050-3_37.
  17. S. Schewe (2008): An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games. In: Proc. 17th Ann. Conf. on Computer Science Logic, CSL'08, LNCS 5213. Springer, pp. 369–384, doi:10.1007/978-3-540-87531-4_27.
  18. H. Seidl (1996): Fast and Simple Nested Fixpoint. Information Processing Letters 59(6), pp. 303–308, doi:10.1016/0020-0190(96)00130-5.
  19. C. Stirling (1995): Local Model Checking Games. In: Proc. 6th Conf. on Concurrency Theory, CONCUR'95, LNCS 962. Springer, pp. 1–11, doi:10.1007/3-540-60218-6_1.
  20. A. Tarski (1955): A Lattice-theoretical Fixpoint Theorem and its Application. Pacific Journal of Mathematics 5, pp. 285–309, doi:10.2140/pjm.1955.5.285.
  21. J. Vöge & M. Jurdziński (2000): A Discrete Strategy Improvement Algorithm for Solving Parity Games. In: Proc. 12th Int. Conf. on Computer Aided Verification, CAV'00, LNCS 1855. Springer, pp. 202–215, doi:10.1007/10722167_18.
  22. I. Walukiewicz (1996): Monadic Second Order Logic on Tree-Like Structures. In: Proc. 13th Ann. Symp. on Theoretical Aspects of Computer Science, STACS'96, Lecture Notes in Computer Science 1046. Springer, pp. 401–413, doi:10.1007/3-540-60922-9_33.
  23. W. Zielonka (1998): Infinite games on finitely coloured graphs with applications to automata on infinite trees. TCS 200(1–2), pp. 135–183, doi:10.1016/S0304-3975(98)00009-7.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org