Currently displaying 1 – 2 of 2

Showing per page

Order by Relevance | Title | Year of publication

Recursive algorithm for parity games requires exponential time

Oliver Friedmann — 2011

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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.

Recursive algorithm for parity games requires exponential time

Oliver Friedmann — 2012

RAIRO - Theoretical Informatics and Applications

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.

Page 1

Download Results (CSV)