References

  1. Pranav Ashok, Krishnendu Chatterjee, Jan Kretínský, Maximilian Weininger & Tobias Winkler (2020): Approximating Values of Generalized-Reachability Stochastic Games. In: LICS. ACM, pp. 102–115, doi:10.1145/3373718.3394761.
  2. Pranav Ashok, Jan Kretínský & Maximilian Weininger (2019): PAC Statistical Model Checking for Markov Decision Processes and Stochastic Games. In: CAV (1), Lecture Notes in Computer Science 11561. Springer, pp. 497–519, doi:10.1007/978-3-030-25540-4_29.
  3. Christel Baier & Joost-Pieter Katoen (2008): Principles of Model Checking. MIT Press.
  4. Christel Baier, Joachim Klein, Linda Leuschner, David Parker & Sascha Wunderlich (2017): Ensuring the Reliability of Your Model Checker: Interval Iteration for Markov Decision Processes. In: CAV (1), Lecture Notes in Computer Science 10426. Springer, pp. 160–180, doi:10.1007/978-3-319-63387-9_8.
  5. Tomás Brázdil, Krishnendu Chatterjee, Martin Chmelik, Vojtech Forejt, Jan Kretínský, Marta Z. Kwiatkowska, David Parker & Mateusz Ujma (2014): Verification of Markov Decision Processes Using Learning Algorithms. In: ATVA, Lecture Notes in Computer Science 8837. Springer, pp. 98–114, doi:10.1007/978-3-319-11936-6_8.
  6. Krishnendu Chatterjee, Luca de Alfaro & Thomas A. Henzinger (2013): Strategy improvement for concurrent reachability and turn-based stochastic safety games. J. Comput. Syst. Sci. 79(5), pp. 640–657, doi:10.1016/j.jcss.2012.12.001.
  7. Krishnendu Chatterjee & Nathanaël Fijalkow (2011): A reduction from parity games to simple stochastic games. In: GandALF, pp. 74–86, doi:10.4204/EPTCS.54.6.
  8. Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen & Rasmus Ibsen-Jensen (2017): Strategy Complexity of Concurrent Safety Games. In: MFCS, LIPIcs 83. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 55:1–55:13, doi:10.4230/LIPIcs.MFCS.2017.55.
  9. Krishnendu Chatterjee & Thomas A. Henzinger (2008): Value Iteration. In: 25 Years of Model Checking, Lecture Notes in Computer Science 5000. Springer, pp. 107–138, doi:10.1007/978-3-540-69850-0_7.
  10. Krishnendu Chatterjee & Thomas A. Henzinger (2012): A survey of stochastic ω-regular games. J. Comput. Syst. Sci. 78(2), pp. 394–413, doi:10.1016/j.jcss.2011.05.002.
  11. Krishnendu Chatterjee, Thomas A. Henzinger, Barbara Jobstmann & Arjun Radhakrishna (2010): Gist: A Solver for Probabilistic Games. In: CAV, Lecture Notes in Computer Science 6174. Springer, pp. 665–669, doi:10.1007/978-3-642-14295-6_57.
  12. Krishnendu Chatterjee, Koushik Sen & Thomas A. Henzinger (2008): Model-Checking omega-Regular Properties of Interval Markov Chains. In: FoSSaCS, Lecture Notes in Computer Science 4962. Springer, pp. 302–317, doi:10.1007/978-3-540-78499-9_22.
  13. Taolue Chen, Vojtech Forejt, Marta Z. Kwiatkowska, Aistis Simaitis & Clemens Wiltsche (2013): On Stochastic Games with Multiple Objectives. In: MFCS, Lecture Notes in Computer Science 8087. Springer, pp. 266–277, doi:10.1007/978-3-642-40313-2_25.
  14. Chih-Hong Cheng, Alois Knoll, Michael Luttenberger & Christian Buckl (2011): GAVS+: An Open Platform for the Research of Algorithmic Game Solving. In: TACAS, Lecture Notes in Computer Science 6605. Springer, pp. 258–261, doi:10.1007/978-3-642-19835-9_22.
  15. Anne Condon (1990): On Algorithms for Simple Stochastic Games. In: Advances In Computational Complexity Theory, DIMACS Series in Discrete Mathematics and Theoretical Computer Science 13. DIMACS/AMS, pp. 51–71, doi:10.1090/dimacs/013/04.
  16. Anne Condon (1992): The Complexity of Stochastic Games. Inf. Comput. 96(2), pp. 203–224, doi:10.1016/0890-5401(92)90048-K.
  17. Costas Courcoubetis & Mihalis Yannakakis (1995): The Complexity of Probabilistic Verification. J. ACM 42(4), pp. 857–907, doi:10.1145/210332.210339.
  18. Decheng Dai & Rong Ge (2011): Another Sub-exponential Algorithm for the Simple Stochastic Game. Algorithmica 61(4), pp. 1092–1104, doi:10.1007/s00453-010-9413-1.
  19. Peng Dai, Mausam, Daniel S. Weld & Judy Goldsmith (2011): Topological Value Iteration Algorithms. J. Artif. Intell. Res. 42, pp. 181–209. Available at http://jair.org/papers/paper3390.html.
  20. J. Filar & K. Vrieze (1997): Competitive Markov Decision Processes. Springer-Verlag.
  21. Hugo Gimbert & Florian Horn (2008): Simple Stochastic Games with Few Random Vertices Are Easy to Solve. In: FoSSaCS, Lecture Notes in Computer Science 4962. Springer, pp. 5–19, doi:10.1007/978-3-540-78499-9_2.
  22. Serge Haddad & Benjamin Monmege (2018): Interval iteration algorithm for MDPs and IMDPs. Theor. Comput. Sci. 735, pp. 111–131, doi:10.1016/j.tcs.2016.12.003.
  23. Ernst Moritz Hahn, Arnd Hartmanns, Christian Hensel, Michaela Klauck, Joachim Klein, Jan Kretínský, David Parker, Tim Quatmann, Enno Ruijters & Marcel Steinmetz (2019): The 2019 Comparison of Tools for the Analysis of Quantitative Formal Models - (QComp 2019 Competition Report). In: TACAS (3), Lecture Notes in Computer Science 11429. Springer, pp. 69–92, doi:10.1007/978-3-030-17502-3_5.
  24. Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen & Peter Bro Miltersen (2014): The Complexity of Solving Reachability Games Using Value and Strategy Iteration. Theory Comput. Syst. 55(2), pp. 380–403, doi:10.1007/s00224-013-9524-6.
  25. Arnd Hartmanns & Benjamin Lucien Kaminski (2020): Optimistic Value Iteration. In: CAV (2), Lecture Notes in Computer Science 12225. Springer, pp. 488–511, doi:10.1007/978-3-030-53291-8_26.
  26. A. J. Hoffman & R. M. Karp (1966): On Nonterminating Stochastic Games. Management Science 12(5), pp. 359–370, doi:10.1287/mnsc.12.5.359.
  27. Rasmus Ibsen-Jensen & Peter Bro Miltersen (2012): Solving Simple Stochastic Games with Few Coin Toss Positions. In: ESA, Lecture Notes in Computer Science 7501. Springer, pp. 636–647, doi:10.1007/978-3-642-33090-2_55.
  28. Mark Kattenbelt, Marta Z. Kwiatkowska, Gethin Norman & David Parker (2010): A game-based abstraction-refinement framework for Markov decision processes. Formal Methods in System Design 36(3), pp. 246–280, doi:10.1007/s10703-010-0097-6.
  29. Edon Kelmendi, Julia Krämer, Jan Kretínský & Maximilian Weininger (2018): Value Iteration for Simple Stochastic Games: Stopping Criterion and Learning Algorithm. In: CAV (1), Lecture Notes in Computer Science 10981. Springer, pp. 623–642, doi:10.1007/978-3-319-96145-3_36.
  30. Mikhail K Kozlov, Sergei P Tarasov & Leonid G Khachiyan (1980): The polynomial solvability of convex quadratic programming. USSR Computational Mathematics and Mathematical Physics 20(5), pp. 223–228, doi:10.1016/0041-5553(80)90098-1.
  31. Jan Kretínský & Tobias Meggendorfer (2017): Efficient Strategy Iteration for Mean Payoff in Markov Decision Processes. In: ATVA, Lecture Notes in Computer Science 10482. Springer, pp. 380–399, doi:10.1007/978-3-319-68167-2_25.
  32. Jan Kretínský & Tobias Meggendorfer (2019): Of Cores: A Partial-Exploration Framework for Markov Decision Processes. In: CONCUR, LIPIcs 140. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 5:1–5:17, doi:10.4230/LIPIcs.CONCUR.2019.5.
  33. Jan Kretínský, Emanuel Ramneantu, Alexander Slivinskiy & Maximilian Weininger (2020): Comparison of Algorithms for Simple Stochastic Games (Full Version). CoRR abs/2008.09465.
  34. Marta Kwiatkowska, Gethin Norman, David Parker & Gabriel Santos (2020): PRISM-games 3.0: Stochastic Game Verification with Concurrency, Equilibria and Time. In: CAV (2), Lecture Notes in Computer Science 12225. Springer, pp. 475–487, doi:10.1007/978-3-030-53291-8_25.
  35. Walter Ludwig (1995): A Subexponential Randomized Algorithm for the Simple Stochastic Game Problem. Inf. Comput. 117(1), pp. 151–155, doi:10.1006/inco.1995.1035.
  36. Martin L. Puterman (1994): Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley Series in Probability and Statistics. Wiley, doi:10.1002/9780470316887.
  37. Tim Quatmann & Joost-Pieter Katoen (2018): Sound Value Iteration. In: CAV (1), Lecture Notes in Computer Science 10981. Springer, pp. 643–661, doi:10.1007/978-3-319-96145-3_37.
  38. Rafal Somla (2005): New Algorithms for Solving Simple Stochastic Games. Electron. Notes Theor. Comput. Sci. 119(1), pp. 51–65, doi:10.1016/j.entcs.2004.07.008.
  39. María Svorenová & Marta Kwiatkowska (2016): Quantitative verification and strategy synthesis for stochastic games. Eur. J. Control 30, pp. 15–30, doi:10.1016/j.ejcon.2016.04.009.
  40. Maximilian Weininger, Tobias Meggendorfer & Jan Kretínský (2019): Satisfiability Bounds for ω-Regular Properties in Bounded-Parameter Markov Decision Processes. In: CDC. IEEE, pp. 2284–2291, doi:10.1109/CDC40024.2019.9029460.
  41. Uri Zwick & Mike Paterson (1996): The Complexity of Mean Payoff Games on Graphs. Theor. Comput. Sci. 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