Permissive strategies: from parity games to safety games
- 1 July 2002
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 36 (3) , 261-275
- https://doi.org/10.1051/ita:2002013
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.Keywords
This publication has 19 references indexed in Scilit:
- Games for synthesis of controllers with partial observationTheoretical Computer Science, 2003
- How much memory is needed to win infinite games?Published by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- Introduction to Discrete Event SystemsPublished by Springer Nature ,1999
- Deciding the winner in parity games is in UP ∩ co-UPInformation Processing Letters, 1998
- Infinite games on finitely coloured graphs with applications to automata on infinite treesTheoretical Computer Science, 1998
- The complexity of mean payoff games on graphsTheoretical Computer Science, 1996
- On model-checking for fragments of μ-calculusPublished by Springer Nature ,1993
- Hierarchies of weak automata and weak monadic formulasTheoretical Computer Science, 1991
- State-strategies for games in Fσδ ∩ GδσThe Journal of Symbolic Logic, 1983
- Trees, automata, and gamesPublished by Association for Computing Machinery (ACM) ,1982