Stochastic Müller games are PSPACE-complete

K. Chatterjee, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007, pp. 436–448.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Series Title
LNCS
Abstract
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 show that both the qualitative and quantitative problem for stochastic Müller games are PSPACE-complete. We also consider two well-known sub-classes of Müller objectives, namely, upward-closed and union-closed objectives, and show that both the qualitative and quantitative problem for these sub-classes are coNP-complete.
Publishing Year
Date Published
2007-12-15
Acknowledgement
This research was supported in part by the the AFOSR MURI grant F49620-00-1- 0327, and the NSF grant CCR-0225610.
Volume
4855
Page
436 - 448
Conference
FSTTCS: Foundations of Software Technology and Theoretical Computer Science
IST-REx-ID

Cite this

Chatterjee K. Stochastic Müller games are PSPACE-complete. In: Vol 4855. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2007:436-448. doi:10.1007/978-3-540-77050-3_36
Chatterjee, K. (2007). Stochastic Müller games are PSPACE-complete (Vol. 4855, pp. 436–448). Presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/978-3-540-77050-3_36
Chatterjee, Krishnendu. “Stochastic Müller Games Are PSPACE-Complete,” 4855:436–48. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007. https://doi.org/10.1007/978-3-540-77050-3_36.
K. Chatterjee, “Stochastic Müller games are PSPACE-complete,” presented at the FSTTCS: Foundations of Software Technology and Theoretical Computer Science, 2007, vol. 4855, pp. 436–448.
Chatterjee K. 2007. Stochastic Müller games are PSPACE-complete. FSTTCS: Foundations of Software Technology and Theoretical Computer Science, LNCS, vol. 4855. 436–448.
Chatterjee, Krishnendu. Stochastic Müller Games Are PSPACE-Complete. Vol. 4855, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2007, pp. 436–48, doi:10.1007/978-3-540-77050-3_36.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar