Stochastic Müller Games are PSPACE-Complete

DOI10.1007/978-3-540-77050-3_36zbMath1135.91333OpenAlexW1579971638MaRDI QIDQ5458855

Krishnendu Chatterjee

Publication date: 24 April 2008

Published in: FSTTCS 2007: Foundations of Software Technology and Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-77050-3_36

Mathematics Subject Classification ID

Games involving graphs (91A43) Other game-theoretic models (91A40) Stochastic games, stochastic differential games (91A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (2)

A survey of stochastic \(\omega \)-regular games ⋮ The complexity of stochastic Müller games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of stochastic Müller games
• The complexity of stochastic games
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• The complexity of mean payoff games on graphs
• Dicing on the Streett
• Supervisory Control of a Class of Discrete Event Processes
• The determinacy of Blackwell games
• Computer Science Logic
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
• Mathematical Foundations of Computer Science 2005
• Solving Sequential Conditions by Finite-State Strategies
• Optimal Strategy Synthesis in Stochastic Müller Games

This page was built for publication: Stochastic Müller Games are PSPACE-Complete