The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

The search session has expired. Please query the service again.

Page 1

Displaying 1 – 3 of 3

Showing per page

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.

Currently displaying 1 – 3 of 3

Page 1