--- _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' ...