Permissive strategies: from parity games to safety games
LaBRI – CNRS – Université de Bordeaux I,
351 cours de la Libération,
33405 Talence Cedex,
Accepted: May 2002
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