2009 | OriginalPaper | Buchkapitel
Reachability in Stochastic Timed Games
verfasst von : Patricia Bouyer, Vojtěch Forejt
Erschienen in: Automata, Languages and Programming
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
We define stochastic timed games, which extend two-player timed games with probabilities (following a recent approach by Baier
et al
), and which extend in a natural way continuous-time Markov decision processes. We focus on the reachability problem for these games, and ask whether one of the players has a strategy to ensure that the probability of reaching a fixed set of states is equal to (or below, resp. above) a certain number
r
, whatever the second player does. We show that the problem is undecidable in general, but that it becomes decidable if we restrict to single-clock 1
$\frac{1}{2}$
-player games and ask whether the player can ensure that the probability of reaching the set is =1 (or >0, =0).