Reachability problems for Markov chains

DOI10.1016/j.ipl.2014.08.013zbMath1302.68204OpenAlexW2114554615MaRDI QIDQ477610

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

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) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (9)

When are emptiness and containment decidable for probabilistic automata? ⋮ Sequential Relational Decomposition ⋮ Decision Questions for Probabilistic Automata on Small Alphabets ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Decidable and expressive classes of probabilistic automata ⋮ The complexity of synchronizing Markov decision processes ⋮ Complexity of Restricted Variants of Skolem and Related Problems ⋮ On eventual non-negativity and positivity for the weighted sum of powers of matrices

Cites Work

• Unnamed Item
• 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
• Positivity Problems for Low-Order Linear Recurrence Sequences
• Approximate Verification of the Symbolic Dynamics of Markov Chains
• Probabilistic automata
• Generalized Automata and Stochastic Languages

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