Logika pro náhodnostní hry

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216224%3A14330%2F07%3A00022945" target="_blank" >RIV/00216224:14330/07:00022945 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Stochastic Game Logic

Popis výsledku v původním jazyce

Stochastic game logic (SGL) is a new temporal logic that combines features of alternating temporal logic (to formalize the individual views and cooperation and reaction facilities of agents in a multiplayer game), probabilistic computation tree logic andextended temporal logic (to reason about qualitative and quantitative, linear or branching time winning objectives). The paper presents the syntax and semantics of SGL and discusses its model checking problem. The model checking problem of SGL turns outto be undecidable when the strategies are history-dependent. We show PSPACE completeness for memoryless deterministic strategies and the EXPSPACE upper bound for memoryless randomized strategies. For the qualitative fragment of SGL we show PSPACE completeness for memoryless strategies.

Název v anglickém jazyce

Stochastic Game Logic

Popis výsledku anglicky

Stochastic game logic (SGL) is a new temporal logic that combines features of alternating temporal logic (to formalize the individual views and cooperation and reaction facilities of agents in a multiplayer game), probabilistic computation tree logic andextended temporal logic (to reason about qualitative and quantitative, linear or branching time winning objectives). The paper presents the syntax and semantics of SGL and discusses its model checking problem. The model checking problem of SGL turns outto be undecidable when the strategies are history-dependent. We show PSPACE completeness for memoryless deterministic strategies and the EXPSPACE upper bound for memoryless randomized strategies. For the qualitative fragment of SGL we show PSPACE completeness for memoryless strategies.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/1M0545" target="_blank" >1M0545: Institut Teoretické Informatiky</a><br>

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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

Fourth International Conference on the Quantitative Evaluation of Systems (QEST 2007)

ISBN

0-7695-2883-X

ISSN

—

e-ISSN

—

Počet stran výsledku

10

Strana od-do

227-236

Název nakladatele

IEEE Computer Society

Místo vydání

Los Alamitos, Washington, Tokyo

Místo konání akce

Edinburgh, Scotland

Datum konání akce

16. 9. 2007

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

WRD - Celosvětová akce

Kód UT WoS článku

—