---
OA_type: closed access
_id: '4553'
abstract:
- lang: eng
  text: 'The theory of graph games with ω-regular winning conditions is the foundation
    for modeling and synthesizing reactive processes. In the case of stochastic reactive
    processes, the corresponding stochastic graph games have three players, two of
    them (System and Environment) behaving adversarially, and the third (Uncertainty)
    behaving probabilistically. We consider two problems for stochastic graph games:
    the qualitative problem asks for the set of states from which a player can win
    with probability 1 (almost-sure winning); the quantitative problem asks for the
    maximal probability of winning (optimal winning) from each state. We show that
    for Rabin winning conditions, both problems are in NP. As these problems were
    known to be NP-hard, it follows that they are NP-complete for Rabin conditions,
    and dually, coNP-complete for Streett conditions. The proof proceeds by showing
    that pure memoryless strategies suffice for qualitatively and quantitatively winning
    stochastic graph games with Rabin conditions. This insight is of interest in its
    own right, as it implies that controllers for Rabin objectives have simple implementations.
    We also prove that for every ω-regular condition, optimal winning strategies are
    no more complex than almost-sure winning strategies.'
acknowledgement: This research was supported in part by the ONR grant N00014-02-1-0671,
  the AFOSR MURI grant F49620-00-1-0327, and the NSF grant CCR-0225610.
alternative_title:
- LNCS
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: Luca
  full_name: De Alfaro, Luca
  last_name: De Alfaro
- 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, De Alfaro L, Henzinger TA. The complexity of stochastic Rabin
    and Streett games. In: <i>32nd International Colloquim on Automata, Languages,
    and Programming</i>. Vol 3580. Springer Nature; 2005:878-890. doi:<a href="https://doi.org/10.1007/11523468_71">10.1007/11523468_71</a>'
  apa: 'Chatterjee, K., De Alfaro, L., &#38; Henzinger, T. A. (2005). The complexity
    of stochastic Rabin and Streett games. In <i>32nd International Colloquim on Automata,
    Languages, and Programming</i> (Vol. 3580, pp. 878–890). Lisbon, Portugal: Springer
    Nature. <a href="https://doi.org/10.1007/11523468_71">https://doi.org/10.1007/11523468_71</a>'
  chicago: Chatterjee, Krishnendu, Luca De Alfaro, and Thomas A Henzinger. “The Complexity
    of Stochastic Rabin and Streett Games.” In <i>32nd International Colloquim on
    Automata, Languages, and Programming</i>, 3580:878–90. Springer Nature, 2005.
    <a href="https://doi.org/10.1007/11523468_71">https://doi.org/10.1007/11523468_71</a>.
  ieee: K. Chatterjee, L. De Alfaro, and T. A. Henzinger, “The complexity of stochastic
    Rabin and Streett games,” in <i>32nd International Colloquim on Automata, Languages,
    and Programming</i>, Lisbon, Portugal, 2005, vol. 3580, pp. 878–890.
  ista: 'Chatterjee K, De Alfaro L, Henzinger TA. 2005. The complexity of stochastic
    Rabin and Streett games. 32nd International Colloquim on Automata, Languages,
    and Programming. ICALP: Automata, Languages and Programming, LNCS, vol. 3580,
    878–890.'
  mla: Chatterjee, Krishnendu, et al. “The Complexity of Stochastic Rabin and Streett
    Games.” <i>32nd International Colloquim on Automata, Languages, and Programming</i>,
    vol. 3580, Springer Nature, 2005, pp. 878–90, doi:<a href="https://doi.org/10.1007/11523468_71">10.1007/11523468_71</a>.
  short: K. Chatterjee, L. De Alfaro, T.A. Henzinger, in:, 32nd International Colloquim
    on Automata, Languages, and Programming, Springer Nature, 2005, pp. 878–890.
conference:
  end_date: 2005-07-15
  location: Lisbon, Portugal
  name: 'ICALP: Automata, Languages and Programming'
  start_date: 2005-07-11
date_created: 2018-12-11T12:09:27Z
date_published: 2005-06-24T00:00:00Z
date_updated: 2026-10-22T13:37:57Z
day: '24'
doi: 10.1007/11523468_71
extern: '1'
fulldoi: https://doi.org/10.1007/11523468_71
intvolume: '      3580'
language:
- iso: eng
month: '06'
oa_version: None
page: 878 - 890
publication: 32nd International Colloquim on Automata, Languages, and Programming
publication_identifier:
  eisbn:
  - '9783540316916'
  isbn:
  - '9783540275800'
publication_status: published
publisher: Springer Nature
publist_id: '158'
status: public
title: The complexity of stochastic Rabin and Streett games
type: conference
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 3580
year: '2005'
...