References

  1. R.Alur, T.A. Henzinger & O.Kupferman (2002): Alternating-Time Temporal Logic.. JACM 49(5), pp. 672–713, doi:10.1145/585265.585270.
  2. K.Apt & E.Grädel (2011): Lectures in Game Theory for Computer Scientists.. Cambridge University Press, doi:10.1017/CBO9780511973468.
  3. L.Babai (2016): Graph Isomorphism in Quasipolynomial Time [Extended Abstract].. In: STOC'16. ACM, pp. 684–697, doi:10.1145/2897518.2897542.
  4. M.Benerecetti, D.Dell'Erba & F.Mogavero: Solving Parity Games via Priority Promotion.. Under submission..
  5. M.Benerecetti, D.Dell'Erba & F.Mogavero (2016): A Delayed Promotion Policy for Parity Games.. In: GANDALF16, EPTCS 226, pp. 30–45, doi:10.4204/EPTCS.226.3.
  6. M.Benerecetti, D.Dell'Erba & F.Mogavero (2016): Improving Priority Promotion for Parity Games.. In: HVC'16, LNCS 10028. Springer, pp. 1–17, doi:10.1007/978-3-319-49052-6_8.
  7. M.Benerecetti, D.Dell'Erba & F.Mogavero (2016): Solving Parity Games via Priority Promotion.. In: CAV'16, LNCS 9780 (Part II). Springer, pp. 270–290, doi:10.1007/978-3-319-41540-6_15.
  8. M.Benerecetti, F.Mogavero & A.Murano (2013): Substructure Temporal Logic.. In: LICS'13. IEEECS, pp. 368–377, doi:10.1109/LICS.2013.43.
  9. M.Benerecetti, F.Mogavero & A.Murano (2015): Reasoning About Substructures and Games.. TOCL 16(3), pp. 25:1–46, doi:10.1109/LICS.2013.43.
  10. D.Berwanger & E.Grädel (2004): Fixed-Point Logics and Solitaire Games.. TCS 37(6), pp. 675–694, doi:10.1007/s00224-004-1147-5.
  11. C.S. Calude, S.Jain, B.Khoussainov, W.Li & F.Stephan (2017): Deciding Parity Games in Quasipolynomial Time.. In: STOC'17. ACM, pp. 252–263, doi:10.1145/3055399.3055409.
  12. K.Chatterjee, T.A. Henzinger & N.Piterman (2010): Strategy Logic.. IC 208(6), pp. 677–693, doi:10.1016/j.ic.2009.07.004.
  13. A.Condon (1992): The Complexity of Stochastic Games.. IC 96(2), pp. 203–224, doi:10.4230/LIPIcs.FSTTCS.2010.505.
  14. A.Ehrenfeucht & J.Mycielski (1979): Positional Strategies for Mean Payoff Games.. IJGT 8(2), doi:10.1007/BF01768705.
  15. E.A. Emerson & C.S. Jutla (1991): Tree Automata, muCalculus, and Determinacy.. In: FOCS'91. IEEECS, pp. 368–377, doi:10.1109/SFCS.1988.21949.
  16. E.A. Emerson, C.S. Jutla & A.P. Sistla (2001): On Model Checking for the muCalculus and its Fragments.. TCS 258(1-2), pp. 491–522, doi:10.1016/S0304-3975(00)00034-7.
  17. E.A. Emerson & C.-L. Lei (1986): Temporal Reasoning Under Generalized Fairness Constraints.. In: STACS'86, LNCS 210. Springer, pp. 267–278, doi:10.1007/3-540-16078-7_62.
  18. J.Fearnley, S.Jain, S.Schewe, F.Stephan & D.Wojtczak (2017): An Ordered Approach to Solving Parity Games in Quasi Polynomial Time and Quasi Linear Space.. In: SPIN'17. ACM, pp. 112–121, doi:10.1145/3092282.3092286.
  19. O.Friedmann (2011): Recursive Algorithm for Parity Games Requires Exponential Time.. RAIROTIA 45(4), pp. 449–457, doi:10.1051/ita/2011124.
  20. O.Friedmann & M.Lange (2009): Solving Parity Games in Practice.. In: ATVA'09, LNCS 5799. Springer, pp. 182–196, doi:10.1007/978-3-642-04761-9_15.
  21. E.Grädel, W.Thomas & T.Wilke (2002): Automata, Logics, and Infinite Games: A Guide to Current Research.. LNCS 2500. Springer, doi:10.1007/3-540-36387-4.
  22. V.A. Gurvich, A.V. Karzanov & L.G. Khachivan (1990): Cyclic Games and an Algorithm to Find Minimax Cycle Means in Directed Graphs.. USSRCMMP 28(5), pp. 85–91, doi:10.1016/0041-5553(88)90012-2.
  23. M.Jurdziński (1998): Deciding the Winner in Parity Games is in UP co-UP.. IPL 68(3), pp. 119–124, doi:10.1016/S0020-0190(98)00150-1.
  24. M.Jurdziński (2000): Small Progress Measures for Solving Parity Games.. In: STACS'00, LNCS 1770. Springer, pp. 290–301, doi:10.1007/3-540-46541-3_24.
  25. M.Jurdziński & R.Lazic (2017): Succinct Progress Measures for Solving Parity Games.. In: LICS'17. ACM, pp. 1–9, doi:10.1109/LICS.2017.8005092.
  26. M.Jurdziński, M.Paterson & U.Zwick (2006): A Deterministic Subexponential Algorithm for Solving Parity Games.. In: SODA'06. SIAM, pp. 117–123, doi:10.1145/1109557.1109571.
  27. M.Jurdziński, M.Paterson & U.Zwick (2008): A Deterministic Subexponential Algorithm for Solving Parity Games.. SJM 38(4), pp. 1519–1532, doi:10.1137/070686652.
  28. N.Klarlund & D.Kozen (1991): Rabin Measures and Their Applications to Fairness and Automata Theory. In: LICS'91. IEEECS, pp. 256–265, doi:10.1109/LICS.1991.151650.
  29. O.Kupferman & M.Y. Vardi (1998): Weak Alternating Automata and Tree Automata Emptiness.. In: STOC'98. ACM, pp. 224–233, doi:10.1145/276698.276748.
  30. A.D. Martin (1975): Borel Determinacy.. AM 102(2), pp. 363–371.
  31. A.D. Martin (1985): A Purely Inductive Proof of Borel Determinacy.. In: SPM'82, Recursion Theory.. AMS and ASL, pp. 303–308.
  32. R.McNaughton (1993): Infinite Games Played on Finite Graphs.. APAL 65, pp. 149–184, doi:10.1016/0168-0072(93)90036-D.
  33. F.Mogavero, A.Murano, G.Perelli & M.Y. Vardi (2012): What Makes ATL* Decidable? A Decidable Fragment of Strategy Logic.. In: CONCUR'12, LNCS 7454. Springer, pp. 193–208, doi:10.1007/978-3-642-32940-1_15.
  34. F.Mogavero, A.Murano, G.Perelli & M.Y. Vardi (2014): Reasoning About Strategies: On the Model-Checking Problem.. TOCL 15(4), pp. 34:1–42, doi:10.1145/2631917.
  35. F.Mogavero, A.Murano, G.Perelli & M.Y. Vardi (2017): Reasoning About Strategies: On the Satisfiability Problem.. LMCS 13(1:9), pp. 1–37, doi:10.23638/LMCS-13(1:9)2017.
  36. F.Mogavero, A.Murano & M.Y. Vardi (2010): Reasoning About Strategies.. In: FSTTCS'10, LIPIcs 8. Leibniz-Zentrum fuer Informatik, pp. 133–144, doi:10.4230/LIPIcs.FSTTCS.2010.133.
  37. A.W. Mostowski (1984): Regular Expressions for Infinite Trees and a Standard Form of Automata.. In: SCT'84, LNCS 208. Springer, pp. 157–168, doi:10.1007/3-540-16066-3_15.
  38. A.W. Mostowski (1991): Games with Forbidden Positions.. Technical Report. University of Gdańsk, Gdańsk, Poland.
  39. D.Neuen & P.Schweitzer (2017): An Exponential Lower Bound for Individualization-Refinement Algorithms for Graph Isomorphism.. Technical Report. arXiv.
  40. D.Neuen & P.Schweitzer (2017): Benchmark Graphs for Practical Graph Isomorphism.. Technical Report. arXiv.
  41. S.Schewe (2007): Solving Parity Games in Big Steps.. In: FSTTCS'07, LNCS 4855. Springer, pp. 449–460, doi:10.1007/978-3-540-77050-3_37.
  42. S.Schewe (2008): ATL* Satisfiability is 2ExpTime-Complete.. In: ICALP'08, LNCS 5126. Springer, pp. 373–385, doi:10.1007/978-3-540-70583-3_31.
  43. S.Schewe & B.Finkbeiner (2006): Satisfiability and Finite Model Property for the Alternating-Time muCalculus.. In: CSL'06, LNCS 6247. Springer, pp. 591–605, doi:10.1007/11874683_39.
  44. J.Vöge & M.Jurdziński (2000): A Discrete Strategy Improvement Algorithm for Solving Parity Games.. In: CAV'00, LNCS 1855. Springer, pp. 202–215, doi:10.1007/10722167_18.
  45. T.Wilke (2001): Alternating Tree Automata, Parity Games, and Modal muCalculus.. BBMS 8(2), pp. 359–391.
  46. 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.
  47. U.Zwick & M.Paterson (1996): The Complexity of Mean Payoff Games on Graphs.. TCS 158(1-2), pp. 343–359, doi:10.1016/0304-3975(95)00188-3.
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org