A survey of stochastic \(\omega \)-regular games

DOI10.1016/j.jcss.2011.05.002zbMath1237.91036OpenAlexW2005684815MaRDI QIDQ414898

Krishnendu Chatterjee, Thomas A. Henzinger

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.05.002

zbMATH Keywords

game theorystochastic games\(\omega \)-regular objectives

Mathematics Subject Classification ID

2-person games (91A05) Games involving graphs (91A43) Stochastic games, stochastic differential games (91A15)

Related Items (37)

On concurrent games with payoff ⋮ Simplifying optimal strategies in \(\limsup\) and \(\liminf\) stochastic games ⋮ Graph Games and Reactive Synthesis ⋮ Symbolic Model Checking in Non-Boolean Domains ⋮ Imperfect information in reactive modules games ⋮ Automatic verification of concurrent stochastic systems ⋮ Quantitative verification and strategy synthesis for stochastic games ⋮ From model checking to equilibrium checking: reactive modules for rational verification ⋮ Model-checking iterated games ⋮ On the relation between reactive synthesis and supervisory control of non-terminating processes ⋮ Mean-payoff games with \(\omega\)-regular specifications ⋮ Verification and Control of Probabilistic Rectangular Hybrid Automata ⋮ Parameterized Algorithms for Parity Games ⋮ Equilibrium in two-player stochastic games with shift-invariant payoffs ⋮ Reachability and safety objectives in Markov decision processes on long but finite horizons ⋮ Automated Verification of Concurrent Stochastic Games ⋮ Symbolic verification and strategy synthesis for turn-based stochastic games ⋮ Symbolic control for stochastic systems via finite parity games ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ On the determinacy of concurrent games on event structures with infinite winning sets ⋮ Verification and control for probabilistic hybrid automata with finite bisimulations ⋮ On the Complexity of Reachability in Parametric Markov Decision Processes ⋮ The complexity of synchronizing Markov decision processes ⋮ Perfect information games where each player acts only once ⋮ Selfish cops and passive robber: qualitative games ⋮ Unnamed Item ⋮ The uniform measure of simple regular sets of infinite trees ⋮ Temporal logic control for stochastic linear systems using abstraction refinement of probabilistic games ⋮ Decoy allocation games on graphs with temporal logic objectives ⋮ Two Variable vs. Linear Temporal Logic in Model Checking and Games ⋮ A note on the Nash equilibria of some multi-player reachability/safety games ⋮ Bounds for synchronizing Markov decision processes ⋮ Iterated Boolean games ⋮ Comparison of algorithms for simple stochastic games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Deciding the winner in parity games is in \(\mathrm{UP}\cap\mathrm{co-UP}\)
• Results on the propositional \(\mu\)-calculus
• Stochastic limit-average games are in EXPTIME
• Number of quantifiers is better than number of tape cells
• Positional strategies for mean payoff games
• The complexity of stochastic games
• Borel determinacy
• Infinite games on finitely coloured graphs with applications to automata on infinite trees
• Infinite games played on finite graphs
• The complexity of mean payoff games on graphs
• Stay-in-a-set games
• Two-player stochastic games. I: A reduction
• Two-player stochastic games. II: The case of recursive games
• Fair simulation
• A subexponential randomized algorithm for the simple stochastic game problem
• Concurrent reachability games
• Play to Test
• Alternating-time temporal logic
• Game Refinement Relations and Metrics
• A deterministic subexponential algorithm for solving parity games
• The complexity of quantitative concurrent parity games
• Algorithms for Omega-Regular Games with Imperfect Information
• Supervisory Control of a Class of Discrete Event Processes
• The Complexity of Markov Decision Processes
• On the menbership problem for functional and multivalued dependencies in relational databases
• The determinacy of Blackwell games
• The Complexity of Tree Automata and Logics of Programs
• The complexity of probabilistic verification
• On the synthesis of strategies in infinite games
• On the synthesis of discrete controllers for timed systems
• Quantitative solution of omega-regular games380872
• Computer Science Logic
• Foundations of Software Science and Computation Structures
• Computer Science Logic
• 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
• Strategy Improvement for Stochastic Rabin and Streett Games
• Optimal Strategy Synthesis in Stochastic Müller Games
• Generalized Parity Games
• Equilibrium points in n -person games
• Stochastic Games
• CONCUR 2005 – Concurrency Theory
• FSTTCS 2005: Foundations of Software Technology and Theoretical Computer Science
• CONCUR 2003 - Concurrency Theory
• Recursive Concurrent Stochastic Games
• Stochastic games

This page was built for publication: A survey of stochastic \(\omega \)-regular games