Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

DOI10.1007/11672142_42MaRDI QIDQ5449826zbMATH OpenOpenAlexFDO

Authors Krishnendu Chatterjee, Thomas A. Henzinger

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11672142_42

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Randomized algorithms (68W20) Stochastic games, stochastic differential games (91A15) Games involving graphs (91A43)

Recommendations

• Strategy Improvement for Stochastic Rabin and Streett Games
• Reduction of stochastic parity to stochastic mean-payoff games
• A randomized subexponential algorithm for parity games
• The complexity of solving stochastic games on graphs
• Quantitative stochastic parity games

Cited in

(18)

• An improved heuristic for the ``Ulam-Rényi game
• A randomized subexponential algorithm for parity games
• Synthesising strategy improvement and recursive algorithms for solving 2.5 player parity games
• Quantitative verification and strategy synthesis for stochastic games
• scientific article; zbMATH DE number 7445162 (Why is no real title available?)
• scientific article; zbMATH DE number 5292473 (Why is no real title available?)
• Value Iteration
• The complexity of solving stochastic games on graphs
• A survey of stochastic -regular games
• The complexity of stochastic Müller games
• Deciding Parity Games in Quasi-polynomial Time
• Improved pseudo-polynomial bound for the value problem and optimal strategy synthesis in mean payoff games
• Computer Science Logic
• A subexponential lower bound for the random facet algorithm for parity games
• Stochastic Müller Games are PSPACE-Complete
• Quantitative stochastic parity games
• Strategy Improvement for Stochastic Rabin and Streett Games
• A direct reduction from stochastic parity games to simple stochastic games

This page was built for publication: Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games

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