Displaying similar documents to “Recursive algorithm for parity games requires exponential time”

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.

Permissive strategies: from parity games to safety games

Julien Bernet, David Janin, Igor Walukiewicz (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

It is proposed to compare strategies in a parity game by comparing the sets of behaviours they allow. For such a game, there may be no winning strategy that encompasses all the behaviours of all winning strategies. It is shown, however, that there always exists a permissive strategy that encompasses all the behaviours of all memoryless strategies. An algorithm for finding such a permissive strategy is presented. Its complexity matches currently known upper bounds for the simpler...