Krishnendu Chatterjee

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2007-110

August 29, 2007

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-110.pdf

The theory of graph games with \omega-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 \omega-regular winning conditions formalized as M\"uller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with M\"uller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies. We study the complexity of stochastic M\"uller games and show that the quantitative analysis problem is PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.

---

BibTeX citation:

@techreport{Chatterjee:EECS-2007-110,
    Author= {Chatterjee, Krishnendu},
    Title= {The Complexity of Stochastic Müller Games},
    Year= {2007},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-110.html},
    Number= {UCB/EECS-2007-110},
    Abstract= {The theory of graph games with \omega-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 \omega-regular winning conditions formalized as M\"uller winning conditions. We present optimal memory bounds for pure (deterministic) almost-sure winning and optimal winning strategies in stochastic graph games with M\"uller winning conditions. We also present improved memory bounds for randomized almost-sure winning and optimal strategies. We study the complexity of stochastic M\"uller games and show that the quantitative analysis problem is PSPACE-complete. Our results are relevant in synthesis of stochastic reactive processes.},
}

EndNote citation:

%0 Report
%A Chatterjee, Krishnendu 
%T The Complexity of Stochastic Müller Games
%I EECS Department, University of California, Berkeley
%D 2007
%8 August 29
%@ UCB/EECS-2007-110
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2007/EECS-2007-110.html
%F Chatterjee:EECS-2007-110