2 Search Results for "Brozek, Vaclav"

Document

DOI: 10.4230/LIPIcs.FSTTCS.2010.108

One-Counter Stochastic Games

Authors: Tomás Brázdil, Václav Brozek, and Kousha Etessami

Published in: LIPIcs, Volume 8, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)

Abstract

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 the transition graph of classic one-counter automata. We study primarily the termination objective, where the goal of one player is 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 that are closely related to some well-studied objectives for stochastic games with rewards. Examples of problems we address include: does player 1 have a strategy to ensure that the counter eventually hits 0, i.e., terminates, almost surely, regardless of what player 2 does? Or that the $liminf$ (or $limsup$) counter value equals $infty$ with a desired probability? Or that the long run average reward is $>0$ with desired probability? We show that the qualitative termination problem for OC-SSGs is in $NP$ intersect $coNP$, and is in P-time for 1-player OC-SSGs, or equivalently for one-counter Markov Decision Processes (OC-MDPs). Moreover, we show that quantitative limit problems for OC-SSGs are in $NP$ intersect $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.

Cite as

Tomás Brázdil, Václav Brozek, and Kousha Etessami. One-Counter Stochastic Games. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010). Leibniz International Proceedings in Informatics (LIPIcs), Volume 8, pp. 108-119, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.FSTTCS.2010.108,
  author =	{Br\'{a}zdil, Tom\'{a}s and Brozek, V\'{a}clav and Etessami, Kousha},
  title =	{{One-Counter Stochastic Games}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2010)},
  pages =	{108--119},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-23-1},
  ISSN =	{1868-8969},
  year =	{2010},
  volume =	{8},
  editor =	{Lodaya, Kamal and Mahajan, Meena},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2010.108},
  URN =		{urn:nbn:de:0030-drops-28571},
  doi =		{10.4230/LIPIcs.FSTTCS.2010.108},
  annote =	{Keywords: one-counter automata, simple stochastic games, Markov decision process, termination, limit, long run average reward}
}

Document

DOI: 10.4230/LIPIcs.STACS.2009.1837

Qualitative Reachability in Stochastic BPA Games

Authors: Tomas Brazdil, Vaclav Brozek, Antonin Kucera, and Jan Obdrzalek

Published in: LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Abstract

We consider a class of infinite-state stochastic games generated by stateless pushdown automata (or, equivalently, 1-exit recursive state machines), where the winning objective is specified by a regular set of target configurations and a qualitative probability constraint `${>}0$' or `${=}1$'. The goal of one player is to maximize the probability of reaching the target set so that the constraint is satisfied, while the other player aims at the opposite. We show that the winner in such games can be determined in $\textbf{NP} \cap \textbf{co-NP}$. Further, we prove that the winning regions for both players are regular, and we design algorithms which compute the associated finite-state automata. Finally, we show that winning strategies can be synthesized effectively.

Cite as

Tomas Brazdil, Vaclav Brozek, Antonin Kucera, and Jan Obdrzalek. Qualitative Reachability in Stochastic BPA Games. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 207-218, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{brazdil_et_al:LIPIcs.STACS.2009.1837,
  author =	{Brazdil, Tomas and Brozek, Vaclav and Kucera, Antonin and Obdrzalek, Jan},
  title =	{{Qualitative Reachability in Stochastic BPA Games}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{207--218},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Albers, Susanne and Marion, Jean-Yves},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1837},
  URN =		{urn:nbn:de:0030-drops-18375},
  doi =		{10.4230/LIPIcs.STACS.2009.1837},
  annote =	{Keywords: Stochastic games, Reachability, Pushdown automata}
}

Refine by Author
1 Brazdil, Tomas
1 Brozek, Vaclav
1 Brozek, Václav
1 Brázdil, Tomás
1 Etessami, Kousha
Show More...

Refine by Classification

Refine by Keyword
1 Markov decision process
1 Pushdown automata
1 Reachability
1 Stochastic games
1 limit
Show More...

Refine by Type
2 document

Refine by Publication Year
1 2009
1 2010

2 Search Results for "Brozek, Vaclav"

One-Counter Stochastic Games

Abstract

Cite as

Qualitative Reachability in Stochastic BPA Games

Abstract

Cite as

Thanks for your feedback!

Could not send message