Permissive strategies: from parity games to safety games

Julien Bernet; David Janin; Igor Walukiewicz

RAIRO - Theoretical Informatics and Applications (2010)

  • 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 36.3 (2010): 261-275. <http://eudml.org/doc/92701>.

@article{Bernet2010,
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},
language = {eng},
month = {3},
number = {3},
pages = {261-275},
publisher = {EDP Sciences},
title = {Permissive strategies: from parity games to safety games},
url = {http://eudml.org/doc/92701},
volume = {36},
year = {2010},
}

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
DA - 2010/3//
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/92701
ER -

References

top
  1. A. Arnold, A. Vincent and I. Walukiewicz, Games for synthesis of controllers with partial observation. Theoret. Comput. Sci. (to appear).  
  2. A. Bergeron, A unified approach to control problems in discrete event processes. RAIRO: Theoret. Informatics Appl.27 (1993) 555-573.  
  3. J.R. Buchi, State strategies for games in F σ δ ∩ G δ σ . J. Symbolic Logic48 (1983) 1171-1198.  
  4. C.G. Cassandras and S. Lafortune, Introduction to Discrete Event Systems. KluwerAcademic Publishers (1999).  
  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).  
  9. Y. Gurevich and L. Harrington, Trees, automata and games, in 14th ACM Symp. on Theory of Computations (1982) 60-65.  
  10. M. Jurdzinski, Deciding the winner in parity games is in UP ∩ co-UP. Inform. Process. Lett.68 (1998) 119-124.  
  11. M. Jurdzinski, Small progress measures for solving parity games, in STACS. Springer, Lecture Notes in Comput. Sci. 1770 (2000) 290-301.  
  12. O. Kupferman, M.Y. Vardi and P. Wolper, An automata-theoretic approach to branching-time model checking. J. ACM 47 (2000).  
  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.  
  14. A.W. Mostowski, Hierarchies of weak automata and week monadic formulas. Theoret. Comput. Sci.83 (1991) 323-335.  
  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.  
  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).  
  19. J. Vöge and M. Jurdzinski, A discrete strategy improvement algorithm for solving parity games (Extended abstract), in CAV. Springer, Lecture Notes in Comput. Sci. 1855 (2000) 202-215.  
  20. W. Zielonka, Infinite games on finitely coloured graphs with applications to automata on infinte trees. Theoret. Comput. Sci.200 (1998) 135-183.  
  21. U. Zwick and M. Paterson, The complexity of mean payoff games on graps. Theoret. Comput. Sci.158 (1996) 343-359.  

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.