A discrete strategy improvement algorithm for solving parity games (extended abstract)
Jens Vöge, Marcin Jurdziński · 2000
A discrete strategy improvement algorithm is given for constructing winning strategies in parity games, thereby providing also a new solution of the model-checking problem for the modal µ-calculus. Known strategy improvement algorithms, as proposed for stochastic games by Hoffman and Karp in 1966, and for discounted payoff games and parity games by Puri in 1995, work with real numbers and require solving linear programming instances involving high precision arithmetic. In the present algorithm for parity games these diculties are avoided by the use of discrete vertex valuations in which information about the relevance of vertices and certain distances is coded. An efficient implemen...