Stochastic Müller games are PSPACE-complete Conference Paper


Author(s): Chatterjee, Krishnendu
Title: Stochastic Müller games are PSPACE-complete
Title Series: LNCS
Affiliation
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.
Conference Title: FSTTCS: Foundations of Software Technology and Theoretical Computer Science
Volume: 4855
Conference Dates: December 12-14, 2007
Conference Location: New Delhi, India
Publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik  
Date Published: 2007-12-15
Start Page: 436
End Page: 448
Sponsor: This research was supported in part by the the AFOSR MURI grant F49620-00-1- 0327, and the NSF grant CCR-0225610.
DOI: 10.1007/978-3-540-77050-3_36
Open access: no
IST Austria Authors
Related IST Austria Work