Expected Reachability-Time Games

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F16%3A00094153" target="_blank" >RIV/00216224:14330/16:00094153 - isvavai.cz</a>
Result on the web
<a href="http://dx.doi.org/10.1016/j.tcs.2016.04.021" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2016.04.021</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2016.04.021" target="_blank" >10.1016/j.tcs.2016.04.021</a>

Result language
angličtina
Original language name
Expected Reachability-Time Games
Original language description
Probabilistic timed automata are a suitable formalism to model systems with real-time, nondeterministic and probabilistic behaviour. We study two-player zero-sum games on such automata where the objective of the game is specified as the expected time to reach a target. The two players---called player Min and player Max---compete by proposing timed moves simultaneously and the move with a shorter delay is performed. The first player attempts to minimise the given objective while the second tries to maximise the objective. We observe that these games are not determined, and study decision problems related to computing the upper and lower values, showing that the problems are decidable and lie in the complexity class NEXPTIME intersection co-NEXPTIME.
Czech name
—
Czech description
—

Type
J<sub>x</sub> - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)
CEP classification
IN - Informatics
OECD FORD branch
—

Project
—
Continuities
I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year
2016
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Similar results(10)