---
OA_type: closed access
_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.
alternative_title:
- Lecture Notes in Computer Science
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  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: Henzinger, Thomas A
  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 nature; 2003:100-113. doi:<a href="https://doi.org/10.1007/978-3-540-45220-1_11">10.1007/978-3-540-45220-1_11</a>'
  apa: 'Chatterjee, K., Jurdziński, M., &#38; Henzinger, T. A. (2003). Simple stochastic
    parity games (Vol. 2803, pp. 100–113). Presented at the CSL: Computer Science
    Logic, Vienna, Austria: Springer nature. <a href="https://doi.org/10.1007/978-3-540-45220-1_11">https://doi.org/10.1007/978-3-540-45220-1_11</a>'
  chicago: Chatterjee, Krishnendu, Marcin Jurdziński, and Thomas A Henzinger. “Simple
    Stochastic Parity Games,” 2803:100–113. Springer nature, 2003. <a href="https://doi.org/10.1007/978-3-540-45220-1_11">https://doi.org/10.1007/978-3-540-45220-1_11</a>.
  ieee: 'K. Chatterjee, M. Jurdziński, and T. A. Henzinger, “Simple stochastic parity
    games,” presented at the CSL: Computer Science Logic, Vienna, Austria, 2003, vol.
    2803, pp. 100–113.'
  ista: 'Chatterjee K, Jurdziński M, Henzinger TA. 2003. Simple stochastic parity
    games. CSL: Computer Science Logic, Lecture Notes in Computer Science, vol. 2803,
    100–113.'
  mla: Chatterjee, Krishnendu, et al. <i>Simple Stochastic Parity Games</i>. Vol.
    2803, Springer nature, 2003, pp. 100–13, doi:<a href="https://doi.org/10.1007/978-3-540-45220-1_11">10.1007/978-3-540-45220-1_11</a>.
  short: K. Chatterjee, M. Jurdziński, T.A. Henzinger, in:, Springer nature, 2003,
    pp. 100–113.
conference:
  end_date: 2003-08-30
  location: Vienna, Austria
  name: 'CSL: Computer Science Logic'
  start_date: 2003-08-25
date_created: 2018-12-11T12:05:46Z
date_published: 2003-08-18T00:00:00Z
date_updated: 2026-05-06T09:31:49Z
day: '18'
doi: 10.1007/978-3-540-45220-1_11
extern: '1'
intvolume: '      2803'
language:
- iso: eng
month: '08'
oa_version: None
page: 100 - 113
publication_identifier:
  eisbn:
  - '9783540452201'
  isbn:
  - '9783540408017'
  issnl:
  - 0302-9743
publication_status: published
publisher: Springer nature
publist_id: '2259'
quality_controlled: '1'
status: public
title: Simple stochastic parity games
type: conference
user_id: ba8df636-2132-11f1-aed0-ed93e2281fdd
volume: 2803
year: '2003'
...