The complexity of solving reachability games using value and strategy iteration

DOI10.1007/s00224-013-9524-6zbMath1319.68149arXiv1007.1812OpenAlexW2567760784MaRDI QIDQ2254503

Peter Bro Miltersen, Rasmus Ibsen-Jensen, Kristoffer Arnsfelt Hansen

Publication date: 5 February 2015

Published in: Theory of Computing Systems, Computer Science – Theory and Applications (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1007.1812

zbMATH Keywords

analysis of algorithmsvalue iterationstrategy iterationconcurrent reachability games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) 2-person games (91A05) Applications of game theory (91A80) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Related Items

Automatic verification of concurrent stochastic systems ⋮ Unnamed Item ⋮ Patience of matrix games ⋮ The complexity of solving reachability games using value and strategy iteration ⋮ Unnamed Item ⋮ Unnamed Item ⋮ New Algorithms for Solving Zero-Sum Stochastic Games ⋮ Qualitative analysis of concurrent mean-payoff games ⋮ Comparison of algorithms for simple stochastic games

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of solving reachability games using value and strategy iteration
• Concurrent reachability games
• Algorithms for discounted stochastic games
• New Results on Simple Stochastic Games
• Existence of p-Equilibrium and Optimal Stationary Strategies in Stochastic Games
• Computer Science Logic
• Exact algorithms for solving stochastic games
• On Nonterminating Stochastic Games
• Discounted and positive stochastic games
• Stochastic Games
• Recursive Concurrent Stochastic Games
• Stochastic games