Reachability in Stochastic Timed Games

• Název česky: Dosažitelnost v pravděpodobnostních časových hrách
• Autoři: BOUYER Patricia; FOREJT Vojtěch
• Rok publikování: 2009
• Druh: Článek ve sborníku
• Konference: Automata, Languages and Programming, 36th Internatilonal Colloquium, ICALP 2009, Rhodes, greece, July 5-12, 2009,Proceedings, Part II
• Fakulta / Pracoviště MU: Fakulta informatiky
• Doi: http://dx.doi.org/10.1007/978-3-642-02930-1_9
• Obor: Informatika
• Klíčová slova: timed systems stochastic systems verification
• Popis: Definujeme stochastické časové hry, které rozšiřují časové hry dvou hráčů o pravděpodobnost a které jsou přirozeným rozšířením Markovových rozhodovacích procesů. Zaměříme se na dosažitelnost v těchto hrách a studujeme otázku, zda má jeden hráčů strategii, která zajistí dosažení určitého stavu s pravděpodobností rovnou (menší než, větší než) dané číslo r. Ukážeme, že problém je obecně nerozhodnutelný, ale že se stane rozhodnutelným, pokud se zaměříme na hry 1 1/2 hráčů s jedněmi hodinami, a ptáme se zda je pravděpodobnost dosažení =1 (nebo >0, =0).

Související projekty

• Institut Teoretické Informatiky
• Matematické a inženýrské metody pro vývoj spolehlivých a bezpečných paralelních a distribuovaných počítačových systémů