---
_id: '3885'
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); and the quantitative problem asks for
the maximal probability of winning (optimal winning) from each state. We consider
ω-regular winning conditions formalized as Müller winning conditions. We present
optimal memory bounds for pure almost-sure winning and optimal winning strategies
in stochastic graph games with Müller winning conditions. We also present improved
memory bounds for randomized almost-sure winning and optimal strategies.'
acknowledgement: This research was supported in part by the the AFOSR MURI grant F49620-00-1-
0327, and the NSF grant CCR-0225610.
alternative_title:
- 'LNCS '
author:
- first_name: Krishnendu
full_name: Krishnendu Chatterjee
id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
last_name: Chatterjee
orcid: 0000-0002-4561-241X
citation:
ama: 'Chatterjee K. Optimal strategy synthesis in stochastic Müller games. In: Vol
4423. Springer; 2007:138-152. doi:10.1007/978-3-540-71389-0_11'
apa: 'Chatterjee, K. (2007). Optimal strategy synthesis in stochastic Müller games
(Vol. 4423, pp. 138–152). Presented at the FoSSaCS: Foundations of Software Science
and Computation Structures, Springer. https://doi.org/10.1007/978-3-540-71389-0_11'
chicago: Chatterjee, Krishnendu. “Optimal Strategy Synthesis in Stochastic Müller
Games,” 4423:138–52. Springer, 2007. https://doi.org/10.1007/978-3-540-71389-0_11.
ieee: 'K. Chatterjee, “Optimal strategy synthesis in stochastic Müller games,” presented
at the FoSSaCS: Foundations of Software Science and Computation Structures, 2007,
vol. 4423, pp. 138–152.'
ista: 'Chatterjee K. 2007. Optimal strategy synthesis in stochastic Müller games.
FoSSaCS: Foundations of Software Science and Computation Structures, LNCS , vol.
4423, 138–152.'
mla: Chatterjee, Krishnendu. Optimal Strategy Synthesis in Stochastic Müller
Games. Vol. 4423, Springer, 2007, pp. 138–52, doi:10.1007/978-3-540-71389-0_11.
short: K. Chatterjee, in:, Springer, 2007, pp. 138–152.
conference:
name: 'FoSSaCS: Foundations of Software Science and Computation Structures'
date_created: 2018-12-11T12:05:42Z
date_published: 2007-07-02T00:00:00Z
date_updated: 2021-01-12T07:52:57Z
day: '02'
doi: 10.1007/978-3-540-71389-0_11
extern: 1
intvolume: ' 4423'
month: '07'
page: 138 - 152
publication_status: published
publisher: Springer
publist_id: '2284'
quality_controlled: 0
status: public
title: Optimal strategy synthesis in stochastic Müller games
type: conference
volume: 4423
year: '2007'
...