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

Abstract

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

How to cite

top

Bernet, 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. [1] A. Arnold, A. Vincent and I. Walukiewicz, Games for synthesis of controllers with partial observation. Theoret. Comput. Sci. (to appear). Zbl1175.93148MR1990739
  2. [2] A. Bergeron, A unified approach to control problems in discrete event processes. RAIRO: Theoret. Informatics Appl. 27 (1993) 555-573. Zbl0807.93002MR1258752
  3. [3] J.R. Buchi, State strategies for games in F σ δ ∩ G δ σ . J. Symbolic Logic 48 (1983) 1171-1198. Zbl0565.03009MR727806
  4. [4] C.G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems. Kluwer Academic Publishers (1999). Zbl0934.93001MR1728175
  5. [5] S. Dziembowski, M. Jurdzinski and I. Walukiewicz, How much memory is needed to win infinite games, in LICS (1997) 99-110. 
  6. [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. Zbl0973.68120
  7. [7] E.A. Emerson and C.S. Jutla, Tree automata, mu-calculus and determinacy, in Proc. FOCS 91 (1991) 368-377. 
  8. [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. [9] Y. Gurevich and L. Harrington, Trees, automata and games, in 14th ACM Symp. on Theory of Computations (1982) 60-65. 
  10. [10] M. Jurdziński, Deciding the winner in parity games is in UP ∩ co-UP. Inform. Process. Lett. 68 (1998) 119-124. Zbl06590783MR1657581
  11. [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. [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. [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. [14] A.W. Mostowski, Hierarchies of weak automata and week monadic formulas. Theoret. Comput. Sci. 83 (1991) 323-335. Zbl0728.68086MR1118576
  15. [15] P.J.G. Ramadge and W.M. Wonham, The control of discrete event systems. Proc. of IEEE 77 (1989). Zbl0595.93047
  16. [16] W. Thomas, Automata on infinite objects, edited by J. van Leeuven. Elsevier, Handb. Theoret. Comput. Sci. B (1990) 133-192. Zbl0900.68316MR1127189
  17. [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. [18] W. Thomas, Languages, automata, and logic, edited by G. Rozenberg and A. Salomaa. Springer-Verlag, Handbook Formal Languages 3 (1997). MR1470024
  19. [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. [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. [21] U. Zwick and M. Paterson, The complexity of mean payoff games on graps. Theoret. Comput. Sci. 158 (1996) 343-359. Zbl0871.68138MR1388974

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.