Recursive algorithm for parity games requires exponential time
Oliver Friedmann (2012)
RAIRO - Theoretical Informatics and 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.