Recursive algorithm for parity games requires exponential time
Oliver Friedmann (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
This paper presents a new lower bound for the recursive algorithm for solving parity games which is induced by the constructive proof of memoryless determinacy by Zielonka. We outline a family of games of linear size on which the algorithm requires exponential time.