Strategy derivation for small progress measures

M.W. Gazda, T.A.C. Willemse

Onderzoeksoutput: Boek/rapportRapportAcademic

28 Downloads (Pure)


Small Progress Measures is one of the most efficient parity game solving algorithms. The original algorithm provides the full solution (winning regions and strategies) in $O(dm \cdot (n/ \lceil d/2 \rceil)^{\lceil d/2 \rceil} )$ time, and requires a re-run of the algorithm on one of the winning regions. We provide a novel operational interpretation of progress measures, and modify the algorithm so that it derives the winning strategies for both players in one pass. This reduces the upper bound on strategy derivation for SPM to $O(dm \cdot (n/ \lceil d/2 \rceil)^{\lceil d/2 \rceil} )$.
Originele taal-2Engels
Aantal pagina's33
StatusGepubliceerd - 2014

Publicatie series

Volume1407.2149 [cs.LO]

Citeer dit

Gazda, M. W., & Willemse, T. A. C. (2014). Strategy derivation for small progress measures. (arXiv; Vol. 1407.2149 [cs.LO]). s.n.