Issue Theoret. Informatics Appl. Volume 36, Number 3, July-September 2002 Page(s) 261 - 275 DOI 10.1051/ita:2002013

Theoret. Informatics Appl. 36, 261-275 (2002)
DOI: 10.1051/ita:2002013

Permissive strategies: from parity games to safety games

Julien Bernet, David Janin and Igor Walukiewicz

LaBRI - CNRS - Université de Bordeaux I, 351 cours de la Libération, 33405 Talence Cedex, France; bernet@labri.fr. janinligw@labri.fr.

(Received February, 2002. Accepted May, 2002.)

Abstract
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 problem of finding the set of winning positions in a parity game. The algorithm can be seen as a reduction of a parity to a safety game and computation of the set of winning positions in the resulting game.

Mathematics Subject Classification. 68Q60, 68Q45, 91A50.


© EDP Sciences 2002

What is OpenURL?