One-Counter Stochastic Games

D 2010

One-Counter Stochastic Games

BRÁZDIL, Tomáš, Václav BROŽEK a Kousha ETESSAMI

Základní údaje

Originální název

One-Counter Stochastic Games

Autoři

BRÁZDIL, Tomáš (203 Česká republika, domácí), Václav BROŽEK (203 Česká republika, garant, domácí) a Kousha ETESSAMI (840 Spojené státy)

Vydání

Dagstuhl, Germany, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010), od s. 108-119, 12 s. 2010

Nakladatel

Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik

Další údaje

Jazyk

angličtina

Typ výsledku

Stať ve sborníku

Obor

10201 Computer sciences, information science, bioinformatics

Stát vydavatele

Německo

Utajení

není předmětem státního či obchodního tajemství

Odkazy

URL URL

Kód RIV

RIV/00216224:14330/10:00044742

Organizační jednotka

Fakulta informatiky

ISBN

978-3-939897-23-1

ISSN

UT WoS

000310361000009

Klíčová slova anglicky

one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward

Příznaky

Mezinárodní význam, Recenzováno

Změněno: 28. 4. 2011 15:13, doc. RNDr. Tomáš Brázdil, Ph.D., MBA

Anotace

V originále

We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on transition graphs of classic one-counter automata. We study primarily the termination objective, where one player has to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives. We show that the qualitative termination problem for OC-SSGs is both in NP and coNP, and in P-time for 1-player OC-SSGs. Moreover, we show that quantitative limit problems for OC-SSGs are both in NP and coNP, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.

Návaznosti

GAP202/10/1469, projekt VaV

Název: Formální metody pro analýzu a verifikaci komplexních systémů

Investor: Grantová agentura ČR, Formální metody pro analýzu a verifikaci komplexních systémů

MSM0021622419, záměr

Název: Vysoce paralelní a distribuované výpočetní systémy

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Vysoce paralelní a distribuované výpočetní systémy

1M0545, projekt VaV

Název: Institut Teoretické Informatiky

Investor: Ministerstvo školství, mládeže a tělovýchovy ČR, Institut Teoretické Informatiky

Citovat

BRÁZDIL, Tomáš, Václav BROŽEK a Kousha ETESSAMI. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2010, s. 108-119. ISBN 978-3-939897-23-1.

@inproceedings{897695,
   author = {Brázdil, Tomáš and Brožek, Václav and Etessami, Kousha},
   address = {Dagstuhl, Germany},
   booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
   keywords = {one-counter automata; simple stochastic games; Markov decision process; termination; long run average reward},
   language = {eng},
   location = {Dagstuhl, Germany},
   isbn = {978-3-939897-23-1},
   pages = {108-119},
   publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
   title = {One-Counter Stochastic Games},
   url = {http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108},
   year = {2010}
}

TY  - CONF
ID  - 897695
AU  - Brázdil, Tomáš - Brožek, Václav - Etessami, Kousha
PY  - 2010
TI  - One-Counter Stochastic Games
PB  - Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik
CY  - Dagstuhl, Germany
SN  - 9783939897231
KW  - one-counter automata
KW  - simple stochastic games
KW  - Markov decision process
KW  - termination
KW  - long run average reward
UR  - http://dx.doi.org/10.4230/LIPIcs.FSTTCS.2010.108
N2  - We study the computational complexity of basic decision problems for one-counter simple stochastic games (OC-SSGs), under various objectives. OC-SSGs are 2-player turn-based stochastic games played on transition graphs of classic one-counter automata. We study primarily the termination objective, where one player has to maximize the probability of reaching counter value 0, while the other player wishes to avoid this. Partly motivated by the goal of understanding termination objectives, we also study certain ``limit'' and ``long run average'' reward objectives. We show that the qualitative termination problem for OC-SSGs is both in NP and coNP, and in P-time for 1-player OC-SSGs. Moreover, we show that quantitative limit problems for OC-SSGs are both in NP and coNP, and are in P-time for 1-player OC-MDPs. Both qualitative limit problems and qualitative termination problems for OC-SSGs are already at least as hard as Condon's quantitative decision problem for finite-state SSGs.
ER  -

BRÁZDIL, Tomáš, Václav BROŽEK a Kousha ETESSAMI. One-Counter Stochastic Games. In \textit{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)}. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, 2010, s.~108-119. ISBN~978-3-939897-23-1.

Přehled o publikaci