Reachability in Stochastic Timed Games

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F09%3A00029567" target="_blank" >RIV/00216224:14330/09:00029567 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/00216224:14330/09:00065859

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Reachability in Stochastic Timed Games

Popis výsledku v původním jazyce

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 &gt;0, =0).

Název v anglickém jazyce

Reachability in Stochastic Timed Games

Popis výsledku anglicky

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 &gt;0, =0).

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2009

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 statě ve sborníku

Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, greece, July 5-12, 2009,Proceedings, Part II

ISBN

978-3-642-02929-5

ISSN

—

e-ISSN

—

Počet stran výsledku

12

Strana od-do

—

Název nakladatele

Springer

Místo vydání

Berlin, Heidelberg, New York

Místo konání akce

Rhodes - Greece

Datum konání akce

5. 7. 2009

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

000270927200009