One-counter Markov decision processes

MaRDI QIDQ5417673zbMATH OpenFDO

Authors Tomáš Brázdil, Václav Brožek, Kousha Etessami, Dominik Wojtczak, Antonin Kučera

Publication date 22 May 2014

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) 2-person games (91A05) Stochastic games, stochastic differential games (91A15) Decision theory for games (91A35)

Recommendations

• Approximating the termination value of one-counter MDPs and stochastic games
• Approximating the termination value of one-counter MDPs and stochastic games
• One-counter stochastic games
• Minimizing expected termination time in one-counter Markov decision processes
• Recursive Markov decision processes and recursive stochastic games

Cited in

(25)

• The Viterbi algorithm for subsets of stochastic context-free languages
• Approximating the termination value of one-counter MDPs and stochastic games
• Simple stochastic games with almost-sure energy-parity objectives are in NP and conp
• Analyzing probabilistic pushdown automata
• Bisimulation equivalence and regularity for real-time one-counter automata
• Mitigating multi-target attacks in hash-based signatures
• Qualitative analysis of VASS-induced MDPs
• One-counter stochastic games
• Ratio and weight quantiles
• Solvency Markov decision processes with interest
• Probabilistic termination by monadic affine sized typing
• Runtime analysis of probabilistic programs with unbounded recursion
• Approximating the termination value of one-counter MDPs and stochastic games
• Minimizing expected termination time in one-counter Markov decision processes
• The odds of staying on budget
• Branching-time model-checking of probabilistic pushdown automata
• Zero-reachability in probabilistic multi-counter automata
• A Survey of Bidding Games on Graphs (Invited Paper)
• Infinite-duration bidding games
• Limit synchronization in Markov decision processes
• Strategy Complexity of Point Payoff, Mean Payoff and Total Payoff Objectives in Countable MDPs
• Positivity-hardness results on Markov decision processes
• On Skolem-hardness and saturation points in Markov decision processes
• Strategy complexity of limsup and liminf threshold objectives in countable MDPs, with applications to optimal expected payoffs
• Runtime analysis of probabilistic programs with unbounded recursion

This page was built for publication: One-counter Markov decision processes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5417673)