---
_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'
...