A List by Author: Jan Obdržálek
Qualitative Reachability in Stochastic BPA Games
A full version of the paper presented at STACS 2009. May 2009, 37 pages.
Available as Postscript,
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 NP intersection 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.