Stochastic games with finitary objectives

K. Chatterjee, T.A. Henzinger, F. Horn, in:, Springer, 2009, pp. 34–54.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published | English
Department
Series Title
LNCS
Abstract
The synthesis of a reactive system with respect to all omega-regular specification requires the solution of a graph game. Such games have been extended in two natural ways. First, a game graph can be equipped with probabilistic choices between alternative transitions, thus allowing the, modeling of uncertain behaviour. These are called stochastic games. Second, a liveness specification can he strengthened to require satisfaction within all unknown but bounded amount of time. These are called finitary objectives. We study. for the first time, the, combination of Stochastic games and finitary objectives. We characterize the requirements on optimal strategies and provide algorithms for Computing the maximal achievable probability of winning stochastic games with finitary parity or Street, objectives. Most notably the set of state's from which a player can win with probability . for a finitary parity objective can he computed in polynomial time even though no polynomial-time algorithm is known in the nonfinitary case.
Publishing Year
Date Published
2009-08-01
Acknowledgement
This research was supported in part by the Swiss National Science Foundation under the Indo-Swiss Joint Research Programme, by the European Network of Excellence on Embedded Systems Design (ArtistDesign), and by the European project Combest.
Volume
5734
Page
34 - 54
Conference
MFCS: Mathematical Foundations of Computer Science
Conference Location
High Tatras, Slovakia
Conference Date
2009-08-24 – 2009-08-28
IST-REx-ID

Cite this

Chatterjee K, Henzinger TA, Horn F. Stochastic games with finitary objectives. In: Vol 5734. Springer; 2009:34-54. doi:10.1007/978-3-642-03816-7_4
Chatterjee, K., Henzinger, T. A., & Horn, F. (2009). Stochastic games with finitary objectives (Vol. 5734, pp. 34–54). Presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia: Springer. https://doi.org/10.1007/978-3-642-03816-7_4
Chatterjee, Krishnendu, Thomas A Henzinger, and Florian Horn. “Stochastic Games with Finitary Objectives,” 5734:34–54. Springer, 2009. https://doi.org/10.1007/978-3-642-03816-7_4.
K. Chatterjee, T. A. Henzinger, and F. Horn, “Stochastic games with finitary objectives,” presented at the MFCS: Mathematical Foundations of Computer Science, High Tatras, Slovakia, 2009, vol. 5734, pp. 34–54.
Chatterjee K, Henzinger TA, Horn F. 2009. Stochastic games with finitary objectives. MFCS: Mathematical Foundations of Computer Science, LNCS, vol. 5734. 34–54.
Chatterjee, Krishnendu, et al. Stochastic Games with Finitary Objectives. Vol. 5734, Springer, 2009, pp. 34–54, doi:10.1007/978-3-642-03816-7_4.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar