Expected Reachability-Time Games

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Expected Reachability-Time Games

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Expected Reachability-Time Games

Popis výsledku anglicky

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.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2016

Kód důvěrnosti údajů

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

Název periodika

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

631

Číslo periodika v rámci svazku

June

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

22

Strana od-do

139-160

Kód UT WoS článku

000377839900007

EID výsledku v databázi Scopus

—