Reachability problems for Markov chains

DOI10.1016/J.IPL.2014.08.013MaRDI QIDQ477610zbMATH OpenOpenAlexFDO

Authors S. Akshay, Timos Antonopoulos, Joël Ouaknine, James Worrell

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ipl.2014.08.013

zbMATH Keywords

Markov chainsformal methodsprobabilistic model checkingpositivity problemSkolem problem

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Recommendations

• scientific article; zbMATH DE number 1956626
• Reachability in Recursive Markov Decision Processes
• Reachability in recursive Markov decision processes
• Reachability in augmented interval Markov chains
• Qualitative reachability for open interval Markov chains
• On Reachability of Markov Chains: A Long-Run Average Approach
• The complexity of reachability in parametric Markov decision processes

Cites work

• scientific article; zbMATH DE number 3823893 (Why is no real title available?)
• A Logic of Probability with Decidable Model Checking
• Approximate verification of the symbolic dynamics of Markov chains
• Approximate verification of the symbolic dynamics of Markov chains
• Generalized Automata and Stochastic Languages
• Occurrence of zero in a linear recursive sequence
• Positivity problems for low-order linear recurrence sequences
• Probabilistic automata

Cited in

(20)

• Undecidable cases of model checking probabilistic temporal-epistemic logic (extended abstract)
• Skolem and positivity completeness of ergodic Markov chains
• On eventual non-negativity and positivity for the weighted sum of powers of matrices
• Positivity-hardness results on Markov decision processes
• Decidable and expressive classes of probabilistic automata
• The complexity of synchronizing Markov decision processes
• Decidability of approximate Skolem problem and applications to logical verification of dynamical properties of Markov chains
• The behavior of a Markov network with respect to an absorbing class: the target algorithm
• Decisive Markov Chains
• The odds of staying on budget
• scientific article; zbMATH DE number 7378586 (Why is no real title available?)
• The complexity of graph-based reductions for reachability in Markov decision processes
• Nested Reachability Approximation for Discrete-Time Markov Chains with Univariate Parameters
• Complexity of Restricted Variants of Skolem and Related Problems
• On the Skolem problem and the Skolem conjecture
• When are emptiness and containment decidable for probabilistic automata?
• Covering problems for Markov chains
• Model checking linear dynamical systems under floating-point rounding
• A probabilistic logic for verifying continuous-time Markov chains
• MDPs as distribution transformers: affine invariant synthesis for safety objectives

This page was built for publication: Reachability problems for Markov chains

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