Citation
Krishnendu Chatterjee. "Stochastic Muller Games are PSPACE-complete". FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science, 436-448, December, 2007.

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

Electronic downloads

• stochmuller.ps · application/postscript · 555 kbytes
• http://dx.doi.org/10.1007/978-3-540-77050-3_36

• HTML

  Krishnendu Chatterjee. <a
  href="http://chess.eecs.berkeley.edu/pubs/465.html"
  >Stochastic Muller Games are PSPACE-complete</a>,
  FSTTCS 2007: Foundations of Software Technology and
  Theoretical Computer Science, 436-448, December, 2007.

• Plain text

  Krishnendu Chatterjee. "Stochastic Muller Games are
  PSPACE-complete". FSTTCS 2007: Foundations of Software
  Technology and Theoretical Computer Science, 436-448,
  December, 2007.

• BibTeX

  @inproceedings{Chatterjee07_StochasticMullerGamesArePSPACEcomplete,
      author = {Krishnendu Chatterjee},
      title = {Stochastic Muller Games are PSPACE-complete},
      booktitle = {FSTTCS 2007: Foundations of Software Technology
                and Theoretical Computer Science},
      pages = {436-448},
      month = {December},
      year = {2007},
      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 Muller winning conditions. We
                present optimal memory bounds for pure
                (deterministic) almost-sure winning and optimal
                winning strategies in stochastic graph games with
                Muller winning conditions. We also present
                improved memory bounds for randomized almost-sure
                winning and optimal strategies. We study the
                complexity of stochastic Muller games and show
                that the quantitative analysis problem is
                PSPACE-complete. Our results are relevant in
                synthesis of stochastic reactive processes.},
      URL = {http://chess.eecs.berkeley.edu/pubs/465.html}
  }
  

Posted by Krishnendu Chatterjee, PhD on 24 Jun 2008.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.