Stochastic Müller Games are PSPACE-Complete

DOI10.1007/978-3-540-77050-3_36MaRDI QIDQ5458855zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• The complexity of stochastic Müller games
• Optimal Strategy Synthesis in Stochastic Müller Games
• Automata, Languages and Programming
• Perfect-information stochastic mean-payoff parity games
• A survey of stochastic -regular games

Cites work

• Borel determinacy
• Computer Science Logic
• Dicing on the Streett
• scientific article; zbMATH DE number 177825 (Why is no real title available?)
• scientific article; zbMATH DE number 549853 (Why is no real title available?)
• scientific article; zbMATH DE number 1134975 (Why is no real title available?)
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Mathematical Foundations of Computer Science 2005
• Optimal Strategy Synthesis in Stochastic Müller Games
• Solving Sequential Conditions by Finite-State Strategies
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
• Supervisory Control of a Class of Discrete Event Processes
• The complexity of mean payoff games on graphs
• The complexity of stochastic games
• The complexity of stochastic Müller games
• The determinacy of Blackwell games

Cited in

(10)

• Explicit Muller games are PTIME
• A survey of stochastic -regular games
• The complexity of stochastic Müller games
• Obligation Blackwell games and p-automata
• Perfect-information stochastic mean-payoff parity games
• Mathematical Foundations of Computer Science 2005
• Automata, Languages and Programming
• Strategy Improvement for Stochastic Rabin and Streett Games
• Optimal Strategy Synthesis in Stochastic Müller Games
• Resolving nondeterminism with randomness

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5458855)