
Evènement pour le groupe Modélisation et Verification
Date  20100701 11:3012:45 
Titre  Solving Simple Stochastic Tail Games 
Résumé  Stochastic games are a natural model for open reactive processes: one player represents the controller and his opponent represents a hostile environnment. The evolution of the system depends on the decisions of the players, supplemented by random transitions. There are two main algorithmic problems on such games: computing the values (quantitative analysis) and deciding whether a player can win with probability 1 (qualitative analysis). In this paper we reduce the quantitative analysis to the qualitative analysis: we provide an algorithm for computing values which uses qualitative analysis as a sub procedure. The correctness proof of this algorithm reveals several nice properties of perfectinformation stochastic tail games, in particular the existence of optimal strategies. We apply these results to games whose winning conditions are boolean combinations of meanpayoff and Buchi conditions. 
Lieu  Salle 076, LaBRI, Rezdechaussée 
Orateur  Florian Horn 
Email  horn@liafa.jussieu.fr 
Url  LIAFA (Paris) 
Aucun document lié à cet événement. RetourRetour à l'index
 