Permissive strategies: from parity games to safety games
Authors:
- 1 July 2002
- journal article
- research article
- Published by EDP Sciences in RAIRO - Theoretical Informatics and Applications
- Vol. 36 (3) , 261-275
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?2002
- Introduction to Discrete Event Systems1999
- 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 μ-calculus1993
- 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 games1982