| Issue |
RAIRO-Theor. Inf. Appl.
Volume 36, Number 3, July/September 2002
|
|
|---|---|---|
| Page(s) | 261 - 275 | |
| DOI | https://doi.org/10.1051/ita:2002013 | |
| Published online | 15 December 2002 | |
Permissive strategies: from parity games to safety games
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
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
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.