Permissive strategies : from parity games to safety games

Bernet, Julien ; Janin, David ; Walukiewicz, Igor

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 36 (2002), p. 261-275 / Harvested from Numdam

Résumé

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.

Détail

Publié le : 2002-01-01

MR 1958243 | Zbl 1090.91514

DOI : https://doi.org/10.1051/ita:2002013
Classification:  68Q60,  68Q45,  91A50

Bibliographie

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

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

[3] J.R. Buchi, State strategies for games in $F_{\sigma \delta }\cap G_{\delta \sigma }$. J. Symbolic Logic 48 (1983) 1171-1198. | MR 727806 | Zbl 0565.03009

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

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

[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 0996.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. | MR 1657581 | Zbl 1338.68109

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

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

[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 827531 | Zbl 0612.68046

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

[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 1127189 | Zbl 0900.68316

[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 1371385

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

[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 0974.68527

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

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