---
_id: '3846'
abstract:
- lang: eng
  text: We summarize classical and recent results about two-player games played on
    graphs with ω-regular objectives. These games have applications in the verification
    and synthesis of reactive systems. Important distinctions are whether a graph
    game is turn-based or concurrent; deterministic or stochastic; zero-sum or not.
    We cluster known results and open problems according to these classifications.
acknowledgement: This research was supported in part by the ONR grant N00014-02-1-0671,
  by the AFOSR MURI grant F49620-00-1-0327, and by the NSF grants CCR-9988172, CCR-0085949,
  and CCR-0225610.
article_processing_charge: No
article_type: original
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- 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, Henzinger TA. A survey of stochastic ω regular games. <i>Journal
    of Computer and System Sciences</i>. 2012;78(2):394-413. doi:<a href="https://doi.org/10.1016/j.jcss.2011.05.002">10.1016/j.jcss.2011.05.002</a>
  apa: Chatterjee, K., &#38; Henzinger, T. A. (2012). A survey of stochastic ω regular
    games. <i>Journal of Computer and System Sciences</i>. Elsevier. <a href="https://doi.org/10.1016/j.jcss.2011.05.002">https://doi.org/10.1016/j.jcss.2011.05.002</a>
  chicago: Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic
    ω Regular Games.” <i>Journal of Computer and System Sciences</i>. Elsevier, 2012.
    <a href="https://doi.org/10.1016/j.jcss.2011.05.002">https://doi.org/10.1016/j.jcss.2011.05.002</a>.
  ieee: K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,”
    <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2. Elsevier, pp.
    394–413, 2012.
  ista: Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games.
    Journal of Computer and System Sciences. 78(2), 394–413.
  mla: Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω
    Regular Games.” <i>Journal of Computer and System Sciences</i>, vol. 78, no. 2,
    Elsevier, 2012, pp. 394–413, doi:<a href="https://doi.org/10.1016/j.jcss.2011.05.002">10.1016/j.jcss.2011.05.002</a>.
  short: K. Chatterjee, T.A. Henzinger, Journal of Computer and System Sciences 78
    (2012) 394–413.
corr_author: '1'
date_created: 2018-12-11T12:05:29Z
date_published: 2012-03-02T00:00:00Z
date_updated: 2025-09-30T07:32:39Z
day: '02'
ddc:
- '000'
department:
- _id: KrCh
- _id: ToHe
doi: 10.1016/j.jcss.2011.05.002
external_id:
  isi:
  - '000299719100002'
file:
- access_level: open_access
  checksum: 241b939deb4517cdd4426d49c67e3fa2
  content_type: application/pdf
  creator: kschuh
  date_created: 2019-01-29T10:54:28Z
  date_updated: 2020-07-14T12:46:17Z
  file_id: '5897'
  file_name: a_survey_of_stochastic_omega-regular_games.pdf
  file_size: 336450
  relation: main_file
file_date_updated: 2020-07-14T12:46:17Z
fulldoi: https://doi.org/10.1016/j.jcss.2011.05.002
has_accepted_license: '1'
intvolume: '        78'
isi: 1
issue: '2'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.1016/j.jcss.2011.05.002
month: '03'
oa: 1
oa_version: Submitted Version
page: 394 - 413
publication: Journal of Computer and System Sciences
publication_status: published
publisher: Elsevier
publist_id: '2341'
quality_controlled: '1'
scopus_import: '1'
status: public
title: A survey of stochastic ω regular games
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 78
year: '2012'
...