The complexity of stochastic Müller games

DOI10.1016/J.IC.2011.11.004MaRDI QIDQ418128zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee

Publication date 24 May 2012

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2011.11.004

zbMATH Keywords

game theorystochastic games\(\omega \)-regular objectivesMüller objectives

Mathematics Subject Classification ID

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

Recommendations

• The complexity of stochastic games
• Stochastic Müller Games are PSPACE-Complete
• Automata, Languages and Programming
• The complexity of solving stochastic games on graphs
• The complexity of ergodic mean-payoff games
• The complexity of Nash equilibria in stochastic multiplayer games
• The complexity of mean payoff games
• Optimal Strategy Synthesis in Stochastic Müller Games
• The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games

Cites work

• 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?)
• scientific article; zbMATH DE number 1980933 (Why is no real title available?)
• Algorithms for stochastic games ? A survey
• Automata, Languages and Programming
• Automata, Languages and Programming
• Computer Science Logic
• Concurrent games with tail objectives
• Dicing on the Streett
• Fixed point characterization of infinite behavior of finite-state systems
• Foundations of Software Science and Computation Structures
• 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
• Quantitative stochastic parity games
• Random fruits on the zielonka tree
• Solving Sequential Conditions by Finite-State Strategies
• Stochastic Müller Games are PSPACE-Complete
• 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 determinacy of Blackwell games

Cited in

(13)

• Optimal Strategy Synthesis in Stochastic Müller Games
• Explicit Muller games are PTIME
• On the Complexity of Non-reversible Betting Games on Many-Valued Events
• scientific article; zbMATH DE number 7340147 (Why is no real title available?)
• Graph Games and Reactive Synthesis
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• Perfect-information stochastic games with generalized mean-payoff objectives
• Random fruits on the zielonka tree
• CEGAR for compositional analysis of qualitative properties in Markov decision processes
• Automata, Languages and Programming
• Stochastic Müller Games are PSPACE-Complete
• Perfect-information stochastic mean-payoff parity games
• Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives

This page was built for publication: The complexity of stochastic Müller games

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