Reduction of stochastic parity to stochastic mean-payoff games

DOI10.1016/j.ipl.2007.08.035zbMath1186.68306OpenAlexW2045519963MaRDI QIDQ963321

Thomas A. Henzinger, Krishnendu Chatterjee

Publication date: 19 April 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.08.035

zbMATH Keywords

stochastic gamesformal methodsparity objectivesmean-payoff objectivesformal verification and model checking

Mathematics Subject Classification ID

Stochastic games, stochastic differential games (91A15) Abstract data types; algebraic specification (68Q65)

Related Items (6)

The Complexity of Synthesis from Probabilistic Components ⋮ On canonical forms for zero-sum stochastic mean payoff games ⋮ A pseudo-polynomial algorithm for mean payoff stochastic games with perfect information and few random positions ⋮ A convex programming-based algorithm for mean payoff stochastic games with perfect information ⋮ Value Iteration ⋮ Model-Free Reinforcement Learning for Stochastic Parity Games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• The complexity of stochastic games
• The complexity of mean payoff games on graphs
• Computer Science Logic
• Foundations of Software Science and Computation Structures
• Stochastic Games with Perfect Information and Time Average Payoff

This page was built for publication: Reduction of stochastic parity to stochastic mean-payoff games