An Optimal Strategy Improvement Algorithm for Solving Parity and Payoff Games

DOI10.1007/978-3-540-87531-4_27zbMath1156.68478OpenAlexW1887255787MaRDI QIDQ3540191

Sven Schewe

Publication date: 20 November 2008

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-87531-4_27

Mathematics Subject Classification ID

Games involving graphs (91A43) Specification and verification (program logics, model checking, etc.) (68Q60)

Related Items

Symmetric Strategy Improvement, The mu-calculus and Model Checking, Graph Games and Reactive Synthesis, From Parity and Payoff Games to Linear Programming, Incentive Stackelberg Mean-Payoff Games, Unnamed Item, Robust worst cases for parity games algorithms, Tropical Linear Regression and Mean Payoff Games: Or, How to Measure the Distance to Equilibria, Synthesising Strategy Improvement and Recursive Algorithms for Solving 2.5 Player Parity Games, Justifications and a reconstruction of parity game solving algorithms, Solving mean-payoff games via quasi dominions, Hyper temporal networks. A tractable generalization of simple temporal networks and its relation to mean payoff games, Unnamed Item, Unnamed Item, Unnamed Item, A superpolynomial lower bound for strategy iteration based on snare memorization, The discrete strategy improvement algorithm for parity games and complexity measures for directed graphs, Solving parity games via priority promotion, Solving Mean-Payoff Games via Quasi Dominions, Unnamed Item, Unnamed Item, Verification of reactive systems via instantiation of parameterised Boolean equation systems, A delayed promotion policy for parity games, Solving Parity Games Using an Automata-Based Algorithm, Solving Parity Games in Practice, Recursive algorithm for parity games requires exponential time