The complexity of stochastic Müller games

DOI10.1016/j.ic.2011.11.004zbMath1238.91022OpenAlexW2162705683MaRDI QIDQ418128

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

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

Related Items (6)

Graph Games and Reactive Synthesis ⋮ Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games ⋮ Unnamed Item ⋮ Average case analysis of the classical algorithm for Markov decision processes with Büchi objectives ⋮ Stochastic Müller Games are PSPACE-Complete ⋮ CEGAR for compositional analysis of qualitative properties in Markov decision processes

Cites Work

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

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