Publications
Publications › References ›
2010
Technical reports
Expected Reachability-Time Games
[FKNT10b]
V. Forejt, M. Kwiatkowska, G. Norman and A. Trivedi.
Expected Reachability-Time Games.
Technical report RR-10-07, Oxford University Computing Laboratory.
June 2010.
pdf bib
- Downloads
PDF 369 KB
BibTeX
- Search for this paper
- Google · Google Scholar
Abstract
In an expected reachability-time game (ERTG) two players, Min and Max, move a
token along the transitions of a probabilistic timed automaton, so as to
minimise and maximise, respectively, the expected time to reach a target.
These games are concurrent since at each step of the game both players choose
a timed move (a time delay and action under their control), and
the transition of the game is determined by the timed move of the player who
proposes the shorter delay.
A game is turn-based if at any step of the game, all available actions
are under the control of precisely one player.
We show that while concurrent ERTGs are not always determined, turn-based ERTGs
are positionally determined.
Using the boundary region graph abstraction, and a generalisation of Asarin
and Maler's simple function,
we show that the decision problems related to computing the upper/lower
values of concurrent ERTGs, and computing the value of turn-based ERTGs are
decidable and their complexity is in NEXPTIME $cap$ co-NEXPTIME.