--- _id: '3897' abstract: - lang: eng text: Many verification, planning, and control problems can be modeled as games played on state-transition graphs by one or two players whose conflicting goals are to form a path in the graph. The focus here is on simple stochastic parity games, that is, two-player games with turn-based probabilistic transitions and omega-regular objectives formalized as parity (Rabin chain) winning conditions. An efficient translation from simple stochastic parity games to nonstochastic parity games is given. As many algorithms are known for solving the latter, the translation yields efficient algorithms for computing the states of a simple stochastic parity game from which a player can win with probability 1. An important special case of simple stochastic parity games are the Markov decision processes with Buchi objectives. For this special case a first provably subquadratic algorithm is given for computing the states from which the single player has a strategy to achieve a Buchi objective with probability 1. For game graphs with m edges the algorithm works in time O(mrootm). Interestingly, a similar technique sheds light on the question of the computational complexity of solving simple Buchi games and yields the first provably subquadratic algorithm, with a running time of O(n(2)/log n) for game graphs with n vertices and O(n) edges. acknowledgement: This research was supported in part by the DARPA grant F33615-C-98-3614, the ONR grant N00014-02-1-0671, the NSF grants CCR-9988172 and CCR-0225610, and the Polish KBN grant 7-T11C-027-20. alternative_title: - LNCS author: - first_name: Krishnendu full_name: Krishnendu Chatterjee id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87 last_name: Chatterjee orcid: 0000-0002-4561-241X - first_name: Marcin full_name: Jurdziński, Marcin last_name: Jurdziński - first_name: Thomas A full_name: Thomas Henzinger id: 40876CD8-F248-11E8-B48F-1D18A9856A87 last_name: Henzinger orcid: 0000−0002−2985−7724 citation: ama: 'Chatterjee K, Jurdziński M, Henzinger TA. Simple stochastic parity games. In: Vol 2803. Springer; 2003:100-113. doi:10.1007/978-3-540-45220-1_11' apa: 'Chatterjee, K., Jurdziński, M., & Henzinger, T. A. (2003). Simple stochastic parity games (Vol. 2803, pp. 100–113). Presented at the CSL: Computer Science Logic, Springer. https://doi.org/10.1007/978-3-540-45220-1_11' chicago: Chatterjee, Krishnendu, Marcin Jurdziński, and Thomas A Henzinger. “Simple Stochastic Parity Games,” 2803:100–113. Springer, 2003. https://doi.org/10.1007/978-3-540-45220-1_11. ieee: 'K. Chatterjee, M. Jurdziński, and T. A. Henzinger, “Simple stochastic parity games,” presented at the CSL: Computer Science Logic, 2003, vol. 2803, pp. 100–113.' ista: 'Chatterjee K, Jurdziński M, Henzinger TA. 2003. Simple stochastic parity games. CSL: Computer Science Logic, LNCS, vol. 2803, 100–113.' mla: Chatterjee, Krishnendu, et al. Simple Stochastic Parity Games. Vol. 2803, Springer, 2003, pp. 100–13, doi:10.1007/978-3-540-45220-1_11. short: K. Chatterjee, M. Jurdziński, T.A. Henzinger, in:, Springer, 2003, pp. 100–113. conference: name: 'CSL: Computer Science Logic' date_created: 2018-12-11T12:05:46Z date_published: 2003-08-18T00:00:00Z date_updated: 2021-01-12T07:53:02Z day: '18' doi: 10.1007/978-3-540-45220-1_11 extern: 1 intvolume: ' 2803' month: '08' page: 100 - 113 publication_status: published publisher: Springer publist_id: '2259' quality_controlled: 0 status: public title: Simple stochastic parity games type: conference volume: 2803 year: '2003' ...