Reachability problems for Markov chains

DOI10.1016/J.IPL.2014.08.013zbMATH Open1302.68204OpenAlexW2114554615MaRDI QIDQ477610FDOQ477610

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

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

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)

Cites Work

• Probabilistic automata
• Positivity problems for low-order linear recurrence sequences
• Occurrence of zero in a linear recursive sequence
• Approximate verification of the symbolic dynamics of Markov chains
• A Logic of Probability with Decidable Model Checking
• Title not available (Why is that?)
• Approximate verification of the symbolic dynamics of Markov chains
• Generalized Automata and Stochastic Languages

Cited In (20)

• Skolem and positivity completeness of ergodic Markov chains
• Undecidable cases of model checking probabilistic temporal-epistemic logic (extended abstract)
• 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
• Title not available (Why is that?)
• 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)