---
res:
bibo_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.@eng'
bibo_authorlist:
- foaf_Person:
foaf_givenName: Krishnendu
foaf_name: Krishnendu Chatterjee
foaf_surname: Chatterjee
foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
orcid: 0000-0002-4561-241X
bibo_doi: 10.1007/978-3-540-77050-3_36
bibo_volume: 4855
dct_date: 2007^xs_gYear
dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
dct_title: Stochastic Müller games are PSPACE-complete@
...