Permissive strategies : from parity games to safety games
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 261-275.

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.

DOI : 10.1051/ita:2002013
Classification : 68Q60, 68Q45, 91A50
@article{ITA_2002__36_3_261_0,
     author = {Bernet, Julien and Janin, David and Walukiewicz, Igor},
     title = {Permissive strategies : from parity games to safety games},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {261--275},
     publisher = {EDP-Sciences},
     volume = {36},
     number = {3},
     year = {2002},
     doi = {10.1051/ita:2002013},
     mrnumber = {1958243},
     zbl = {1090.91514},
     language = {en},
     url = {http://www.numdam.org/articles/10.1051/ita:2002013/}
}
TY  - JOUR
AU  - Bernet, Julien
AU  - Janin, David
AU  - Walukiewicz, Igor
TI  - Permissive strategies : from parity games to safety games
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2002
SP  - 261
EP  - 275
VL  - 36
IS  - 3
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita:2002013/
DO  - 10.1051/ita:2002013
LA  - en
ID  - ITA_2002__36_3_261_0
ER  - 
%0 Journal Article
%A Bernet, Julien
%A Janin, David
%A Walukiewicz, Igor
%T Permissive strategies : from parity games to safety games
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2002
%P 261-275
%V 36
%N 3
%I EDP-Sciences
%U http://www.numdam.org/articles/10.1051/ita:2002013/
%R 10.1051/ita:2002013
%G en
%F ITA_2002__36_3_261_0
Bernet, Julien; Janin, David; Walukiewicz, Igor. Permissive strategies : from parity games to safety games. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002) no. 3, pp. 261-275. doi : 10.1051/ita:2002013. http://www.numdam.org/articles/10.1051/ita:2002013/

[1] A. Arnold, A. Vincent and I. Walukiewicz, Games for synthesis of controllers with partial observation. Theoret. Comput. Sci. (to appear). | MR

[2] A. Bergeron, A unified approach to control problems in discrete event processes. RAIRO: Theoret. Informatics Appl. 27 (1993) 555-573. | Numdam | MR | Zbl

[3] J.R. Buchi, State strategies for games in F σδ G δσ . J. Symbolic Logic 48 (1983) 1171-1198. | MR | Zbl

[4] C.G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems. Kluwer Academic Publishers (1999). | MR | Zbl

[5] S. Dziembowski, M. Jurdzinski and I. Walukiewicz, How much memory is needed to win infinite games, in LICS (1997) 99-110.

[6] E.A. Emerson, C. Jutla and A. Sistla, On model-checking for fragments of μ-calculus, in CAV'93. Springer, Lecture Notes in Comput. Sci. 697 (1993) 385-396.

[7] E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS 91 (1991) 368-377.

[8] O. Grumberg, T. Heyman and A. Schusterk, Distributed symbolic model checking for mu-calculus, in CAV'01. Springer, Lecture Notes in Comput. Sci. 2102 (2001). | Zbl

[9] Y. Gurevich and L. Harrington, Trees, automata and games, in 14th ACM Symp. on Theory of Computations (1982) 60-65.

[10] M. Jurdziński, Deciding the winner in parity games is in UPco-UP. Inform. Process. Lett. 68 (1998) 119-124. | MR | Zbl

[11] M. Jurdziński, Small progress measures for solving parity games, in STACS. Springer, Lecture Notes in Comput. Sci. 1770 (2000) 290-301. | MR | Zbl

[12] O. Kupferman, M.Y. Vardi and P. Wolper, An automata-theoretic approach to branching-time model checking. J. ACM 47 (2000). | MR | Zbl

[13] A.W. Mostowski, Regular expressions for infinite trees and a standard form of automata, edited by A. Skowron, in Fifth Symposium on Computation Theory. Springer, Lecture Notes in Comput. Sci. 208 (1984) 157-168. | MR | Zbl

[14] A.W. Mostowski, Hierarchies of weak automata and week monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. | MR | Zbl

[15] P.J.G. Ramadge and W.M. Wonham, The control of discrete event systems. Proc. of IEEE 77 (1989).

[16] W. Thomas, Automata on infinite objects, edited by J. van Leeuven. Elsevier, Handb. Theoret. Comput. Sci. B (1990) 133-192. | MR | Zbl

[17] W. Thomas, On the synthesis of strategies in infinite games, in STACS '95. Springer, Lecture Notes in Comput. Sci. 900 (1995) 1-13. | MR

[18] W. Thomas, Languages, automata, and logic, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Handbook Formal Languages 3 (1997). | MR

[19] J. Vöge and M. Jurdziński, A discrete strategy improvement algorithm for solving parity games (Extended abstract), in CAV. Springer, Lecture Notes in Comput. Sci. 1855 (2000) 202-215. | Zbl

[20] W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinte trees. Theoret. Comput. Sci. 200 (1998) 135-183. | MR | Zbl

[21] U. Zwick and M. Paterson, The complexity of mean payoff games on graps. Theoret. Comput. Sci. 158 (1996) 343-359. | MR | Zbl

Cité par Sources :