"We consider a class of infinite-state Markov decision processes generated by stateless pushdown automata. This class corresponds to 1.5-player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets S and T of safe and terminal stack configurations, where the membership to S and T depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given x in {0,1}. We show that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states." . . . "[02FB1C3C44F7]" . "Markov decision processes; temporal logics; reachability"@en . "Bro\u017Eek, V\u00E1clav" . . "391530" . . "Reachability in Recursive Markov Decision Processes" . "18"^^ . . "Reachability in Recursive Markov Decision Processes"@en . "000256002800003" . . "P(1M0545), P(GD102/05/H050), Z(MSM0021622419)" . "Reachability in Recursive Markov Decision Processes"@en . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . . "5" . . . "4"^^ . "Forejt, Vojt\u011Bch" . "Br\u00E1zdil, Tom\u00E1\u0161" . . . "0890-5401" . "Information and Computation" . "Ku\u010Dera, Anton\u00EDn" . . . "Reachability in Recursive Markov Decision Processes" . "4"^^ . "14330" . "RIV/00216224:14330/08:00024683" . . . . "206" . . . "We consider a class of infinite-state Markov decision processes generated by stateless pushdown automata. This class corresponds to 1.5-player games over graphs generated by BPA systems or (equivalently) 1-exit recursive state machines. An extended reachability objective is specified by two sets S and T of safe and terminal stack configurations, where the membership to S and T depends just on the top-of-the-stack symbol. The question is whether there is a suitable strategy such that the probability of hitting a terminal configuration by a path leading only through safe configurations is equal to (or different from) a given x in {0,1}. We show that the qualitative extended reachability problem is decidable in polynomial time, and that the set of all configurations for which there is a winning strategy is effectively regular. More precisely, this set can be represented by a deterministic finite-state automaton with a fixed number of control states."@en . "RIV/00216224:14330/08:00024683!RIV10-GA0-14330___" . . . .