A survey of stochastic ω regular games

Chatterjee, Krishnendu; Henzinger, Thomas A

A survey of stochastic ω regular games

Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 78(2), 394–413.

Download

a_survey_of_stochastic_omega-regular_games.pdf 336.45 KB [Submitted Version]

Download (ext.)

https://doi.org/10.1016/j.jcss.2011.05.002 [Submitted Version]

DOI

10.1016/j.jcss.2011.05.002

Journal Article | Published | English

Scopus indexed

Author

Chatterjee, Krishnendu^ISTA ; Henzinger, Thomas A^ISTA

Corresponding author has ISTA affiliation

Department

Chatterjee Group
Henzinger_Thomas Group

Abstract

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.

Publishing Year

2012

Date Published

2012-03-02

Journal Title

Journal of Computer and System Sciences

Publisher

Elsevier

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.

Volume

Issue

Page

394 - 413

IST-REx-ID

3846

Cite this

Chatterjee K, Henzinger TA. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 2012;78(2):394-413. doi:10.1016/j.jcss.2011.05.002

Chatterjee, K., & Henzinger, T. A. (2012). A survey of stochastic ω regular games. Journal of Computer and System Sciences. Elsevier. https://doi.org/10.1016/j.jcss.2011.05.002

Chatterjee, Krishnendu, and Thomas A Henzinger. “A Survey of Stochastic ω Regular Games.” Journal of Computer and System Sciences. Elsevier, 2012. https://doi.org/10.1016/j.jcss.2011.05.002.

K. Chatterjee and T. A. Henzinger, “A survey of stochastic ω regular games,” Journal of Computer and System Sciences, vol. 78, no. 2. Elsevier, pp. 394–413, 2012.

Chatterjee K, Henzinger TA. 2012. A survey of stochastic ω regular games. Journal of Computer and System Sciences. 78(2), 394–413.

Chatterjee, Krishnendu, and Thomas A. Henzinger. “A Survey of Stochastic ω Regular Games.” Journal of Computer and System Sciences, vol. 78, no. 2, Elsevier, 2012, pp. 394–413, doi:10.1016/j.jcss.2011.05.002.

All files available under the following license(s):

Copyright Statement: