The complexity of stochastic Müller games

DOI10.1016/J.IC.2011.11.004zbMATH Open1238.91022OpenAlexW2162705683MaRDI QIDQ418128FDOQ418128

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

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

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)

Cites Work

• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Algorithms for stochastic games ? A survey
• Title not available (Why is that?)
• The determinacy of Blackwell games
• Mathematical Foundations of Computer Science 2005
• Supervisory Control of a Class of Discrete Event Processes
• Title not available (Why is that?)
• Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games
• Quantitative stochastic parity games
• Automata, Languages and Programming
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Title not available (Why is that?)
• Automata, Languages and Programming
• Fixed point characterization of infinite behavior of finite-state systems
• Dicing on the Streett
• Concurrent games with tail objectives
• Title not available (Why is that?)
• Computer Science Logic
• Foundations of Software Science and Computation Structures
• Random fruits on the zielonka tree
• Stochastic Müller Games are PSPACE-Complete
• Solving Sequential Conditions by Finite-State Strategies
• Optimal Strategy Synthesis in Stochastic Müller Games

Cited In (14)

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

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)