References

  1. David Avis & Oliver Friedmann (2017): An exponential lower bound for Cunningham's rule. Math. Program. 161(1-2), pp. 271–305, doi:10.1007/s10107-016-1008-4.
  2. Massimo Benerecetti, Daniele Dell'Erba & Fabio Mogavero (2016): A Delayed Promotion Policy for Parity Games. In: GandALF 2016, EPTCS 226, pp. 30–45, doi:10.4204/EPTCS.226.3.
  3. Massimo Benerecetti, Daniele Dell'Erba & Fabio Mogavero (2016): Improving Priority Promotion for Parity Games. In: HVC 2016, LNCS 10028, pp. 117–133, doi:10.1007/978-3-319-49052-6_8.
  4. Massimo Benerecetti, Daniele Dell'Erba & Fabio Mogavero (2016): Solving Parity Games via Priority Promotion. In: CAV 2016, LNCS 9780. Springer, pp. 270–290, doi:10.1007/978-3-319-41540-6_15.
  5. Massimo Benerecetti, Daniele Dell'Erba & Fabio Mogavero (2017): Robust Exponential Worst Cases for Divide-et-Impera Algorithms for Parity Games. In: GandALF, EPTCS 256, pp. 121–135, doi:10.4204/EPTCS.256.9.
  6. Massimo Benerecetti, Daniele Dell'Erba & Fabio Mogavero (2018): Solving parity games via priority promotion. Formal Methods in System Design 52(2), pp. 193–226, doi:10.1007/s10703-018-0315-1.
  7. Florian Bruse, Michael Falk & Martin Lange (2014): The Fixpoint-Iteration Algorithm for Parity Games. In: GandALF, EPTCS 161, pp. 116–130, doi:10.4204/EPTCS.161.12.
  8. Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li & Frank Stephan (2017): Deciding parity games in quasipolynomial time. In: STOC. ACM, pp. 252–263, doi:10.1145/3055399.3055409.
  9. Tom van Dijk (2018): Attracting Tangles to Solve Parity Games. In: CAV (2), LNCS 10982. Springer, pp. 198–215, doi:10.1007/978-3-319-96142-2_14.
  10. Tom van Dijk (2018): Oink: An Implementation and Evaluation of Modern Parity Game Solvers. In: TACAS (1), LNCS 10805. Springer, pp. 291–308, doi:10.1007/978-3-319-89960-2_16.
  11. Tom van Dijk & Bob Rubbens (2019): Simple Fixpoint Iteration to Solve Parity Games. Accepted at GandALF 2019.
  12. E. Allen Emerson & Charanjit S. Jutla (1991): Tree Automata, Mu-Calculus and Determinacy (Extended Abstract). In: FOCS. IEEE Computer Society, pp. 368–377, doi:10.1109/SFCS.1991.185392.
  13. E. Allen Emerson, Charanjit S. Jutla & A. Prasad Sistla (2001): On model checking for the mu-calculus and its fragments. Theor. Comput. Sci. 258(1-2), pp. 491–522, doi:10.1016/S0304-3975(00)00034-7.
  14. John Fearnley (2010): Non-oblivious Strategy Improvement. In: LPAR (Dakar), LNCS 6355. Springer, pp. 212–230, doi:10.1007/978-3-642-17511-4_13.
  15. John Fearnley (2017): Efficient Parallel Strategy Improvement for Parity Games. In: CAV (2), LNCS 10427. Springer, pp. 137–154, doi:10.1007/978-3-319-63390-9_8.
  16. John Fearnley, Sanjay Jain, Bart de Keijzer, Sven Schewe, Frank Stephan & Dominik Wojtczak (2019): An ordered approach to solving parity games in quasi-polynomial time and quasi-linear space. STTT 21(3), pp. 325–349, doi:10.1007/s10009-019-00509-3.
  17. John Fearnley & Rahul Savani (2016): The Complexity of All-switches Strategy Improvement. In: SODA. SIAM, pp. 130–139, doi:10.1137/1.9781611974331.ch10.
  18. Oliver Friedmann (2009): An Exponential Lower Bound for the Parity Game Strategy Improvement Algorithm as We Know it. In: LICS. IEEE Computer Society, pp. 145–156, doi:10.1109/LICS.2009.27.
  19. Oliver Friedmann (2011): An Exponential Lower Bound for the Latest Deterministic Strategy Iteration Algorithms. Logical Methods in Computer Science 7(3), doi:10.2168/LMCS-7(3:23)2011.
  20. Oliver Friedmann (2011): Recursive algorithm for parity games requires exponential time. RAIRO - Theor. Inf. and Applic. 45(4), pp. 449–457, doi:10.1051/ita/2011124.
  21. Oliver Friedmann (2011): A Subexponential Lower Bound for Zadeh's Pivoting Rule for Solving Linear Programs and Games. In: IPCO, Lecture Notes in Computer Science 6655. Springer, pp. 192–206, doi:10.1007/978-3-642-20807-2_16.
  22. Oliver Friedmann (2012): A subexponential lower bound for the Least Recently Considered rule for solving linear programs and games. In: GAMES.
  23. Oliver Friedmann (2013): A superpolynomial lower bound for strategy iteration based on snare memorization. Discrete Applied Mathematics 161(10-11), pp. 1317–1337, doi:10.1016/j.dam.2013.02.007.
  24. Oliver Friedmann, Thomas Dueholm Hansen & Uri Zwick (2011): A subexponential lower bound for the Random Facet algorithm for Parity Games. In: SODA. SIAM, pp. 202–216, doi:10.1137/1.9781611973082.19.
  25. Oliver Friedmann & Martin Lange (2009): Solving Parity Games in Practice. In: ATVA, LNCS 5799. Springer, pp. 182–196, doi:10.1007/978-3-642-04761-9_15.
  26. Maciej Gazda & Tim A. C. Willemse (2013): Zielonka's Recursive Algorithm: dull, weak and solitaire games and tighter bounds. In: GandALF, EPTCS 119, pp. 7–20, doi:10.4204/EPTCS.119.4.
  27. Erich Grädel, Wolfgang Thomas & Thomas Wilke (2002): Automata, Logics, and Infinite Games: A Guide to Current Research. LNCS 2500. Springer, doi:10.1007/3-540-36387-4.
  28. Marcin Jurdzinski (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.
  29. Marcin Jurdzinski (2000): Small Progress Measures for Solving Parity Games. In: STACS, LNCS 1770. Springer, pp. 290–301, doi:10.1007/3-540-46541-3_24.
  30. Marcin Jurdzinski & Ranko Lazic (2017): Succinct progress measures for solving parity games. In: LICS. IEEE Computer Society, pp. 1–9, doi:10.1109/LICS.2017.8005092.
  31. Dexter Kozen (1983): Results on the Propositional mu-Calculus. Theor. Comput. Sci. 27, pp. 333–354, doi:10.1016/0304-3975(82)90125-6.
  32. Orna Kupferman & Moshe Y. Vardi (1998): Weak Alternating Automata and Tree Automata Emptiness. In: STOC. ACM, pp. 224–233, doi:10.1145/276698.276748.
  33. Robert McNaughton (1993): Infinite Games Played on Finite Graphs. Ann. Pure Appl. Logic 65(2), pp. 149–184, doi:10.1016/0168-0072(93)90036-D.
  34. Philipp J. Meyer, Salomon Sickert & Michael Luttenberger (2018): Strix: Explicit Reactive Synthesis Strikes Back!. In: CAV (1), Lecture Notes in Computer Science 10981. Springer, pp. 578–586, doi:10.1007/978-3-319-96145-3_31.
  35. Pawel Parys (2019): Parity Games: Zielonka's Algorithm in Quasi-Polynomial Time. CoRR abs/1904.12446.
  36. Antonio Di Stasio, Aniello Murano, Giuseppe Perelli & Moshe Y. Vardi (2016): Solving Parity Games Using an Automata-Based Algorithm. In: CIAA, LNCS 9705. Springer, pp. 64–76, doi:10.1007/978-3-319-40946-7_6.
  37. Wieslaw Zielonka (1998): Infinite Games on Finitely Coloured Graphs with Applications to Automata on Infinite Trees. Theor. Comput. Sci. 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