Reachability in Stochastic Timed Games.
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...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Conference item |
| Published: |
Springer
2009
|
| _version_ | 1797081298838224896 |
|---|---|
| author | Bouyer, P Forejt, V |
| author2 | Albers, S |
| author_facet | Albers, S Bouyer, P Forejt, V |
| author_sort | Bouyer, P |
| collection | OXFORD |
| description | 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 1/2-player games and ask whether the player can ensure that the probability of reaching the set is =1 (or >0, =0). © 2009 Springer Berlin Heidelberg. |
| first_indexed | 2024-03-07T01:12:40Z |
| format | Conference item |
| id | oxford-uuid:8d925ab2-4bec-4d4b-ab2b-f62b16bef8e0 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T01:12:40Z |
| publishDate | 2009 |
| publisher | Springer |
| record_format | dspace |
| spelling | oxford-uuid:8d925ab2-4bec-4d4b-ab2b-f62b16bef8e02022-03-26T22:52:02ZReachability in Stochastic Timed Games.Conference itemhttp://purl.org/coar/resource_type/c_5794uuid:8d925ab2-4bec-4d4b-ab2b-f62b16bef8e0Symplectic Elements at OxfordSpringer2009Bouyer, PForejt, VAlbers, SMarchetti-Spaccamela, AMatias, YNikoletseas, SEThomas, WWe 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 1/2-player games and ask whether the player can ensure that the probability of reaching the set is =1 (or >0, =0). © 2009 Springer Berlin Heidelberg. |
| spellingShingle | Bouyer, P Forejt, V Reachability in Stochastic Timed Games. |
| title | Reachability in Stochastic Timed Games. |
| title_full | Reachability in Stochastic Timed Games. |
| title_fullStr | Reachability in Stochastic Timed Games. |
| title_full_unstemmed | Reachability in Stochastic Timed Games. |
| title_short | Reachability in Stochastic Timed Games. |
| title_sort | reachability in stochastic timed games |
| work_keys_str_mv | AT bouyerp reachabilityinstochastictimedgames AT forejtv reachabilityinstochastictimedgames |