# Permissive strategies : from parity games to safety games

Julien Bernet; David Janin; Igor Walukiewicz

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2002)

- Volume: 36, Issue: 3, page 261-275
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topBernet, Julien, Janin, David, and Walukiewicz, Igor. "Permissive strategies : from parity games to safety games." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 36.3 (2002): 261-275. <http://eudml.org/doc/244731>.

@article{Bernet2002,

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.},

author = {Bernet, Julien, Janin, David, Walukiewicz, Igor},

journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},

language = {eng},

number = {3},

pages = {261-275},

publisher = {EDP-Sciences},

title = {Permissive strategies : from parity games to safety games},

url = {http://eudml.org/doc/244731},

volume = {36},

year = {2002},

}

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

PB - EDP-Sciences

VL - 36

IS - 3

SP - 261

EP - 275

AB - 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.

LA - eng

UR - http://eudml.org/doc/244731

ER -

## References

top- [1] A. Arnold, A. Vincent and I. Walukiewicz, Games for synthesis of controllers with partial observation. Theoret. Comput. Sci. (to appear). Zbl1175.93148MR1990739
- [2] A. Bergeron, A unified approach to control problems in discrete event processes. RAIRO: Theoret. Informatics Appl. 27 (1993) 555-573. Zbl0807.93002MR1258752
- [3] J.R. Buchi, State strategies for games in ${F}_{\sigma \delta}\cap {G}_{\delta \sigma}$. J. Symbolic Logic 48 (1983) 1171-1198. Zbl0565.03009MR727806
- [4] C.G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems. Kluwer Academic Publishers (1999). Zbl0934.93001MR1728175
- [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 $\mu $-calculus, in CAV’93. Springer, Lecture Notes in Comput. Sci. 697 (1993) 385-396. Zbl0973.68120
- [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). Zbl0996.68106
- [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 UP$\cap $co-UP. Inform. Process. Lett. 68 (1998) 119-124. Zbl06590783MR1657581
- [11] M. Jurdziński, Small progress measures for solving parity games, in STACS. Springer, Lecture Notes in Comput. Sci. 1770 (2000) 290-301. Zbl0962.68111MR1781740
- [12] O. Kupferman, M.Y. Vardi and P. Wolper, An automata-theoretic approach to branching-time model checking. J. ACM 47 (2000). Zbl1133.68376MR1769445
- [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. Zbl0612.68046MR827531
- [14] A.W. Mostowski, Hierarchies of weak automata and week monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. Zbl0728.68086MR1118576
- [15] P.J.G. Ramadge and W.M. Wonham, The control of discrete event systems. Proc. of IEEE 77 (1989). Zbl0595.93047
- [16] W. Thomas, Automata on infinite objects, edited by J. van Leeuven. Elsevier, Handb. Theoret. Comput. Sci. B (1990) 133-192. Zbl0900.68316MR1127189
- [17] W. Thomas, On the synthesis of strategies in infinite games, in STACS ’95. Springer, Lecture Notes in Comput. Sci. 900 (1995) 1-13.
- [18] W. Thomas, Languages, automata, and logic, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Handbook Formal Languages 3 (1997). MR1470024
- [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. Zbl0974.68527
- [20] W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinte trees. Theoret. Comput. Sci. 200 (1998) 135-183. Zbl0915.68120MR1625527
- [21] U. Zwick and M. Paterson, The complexity of mean payoff games on graps. Theoret. Comput. Sci. 158 (1996) 343-359. Zbl0871.68138MR1388974

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.