Skolem and positivity completeness of ergodic Markov chains

DOI10.1016/J.IPL.2024.106481MaRDI QIDQ6551702zbMATH OpenFDO

Authors Mihir Vahanwala

Publication date 7 June 2024

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

zbMATH Keywords

model checkingreachabilityformal methodslinear recurrence sequencesergodic Markov chains

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)

Recommendations

• Reachability problems for Markov chains
• Decidability of approximate Skolem problem and applications to logical verification of dynamical properties of Markov chains
• Decisive Markov Chains
• Complexity of Restricted Variants of Skolem and Related Problems
• Approximate verification of the symbolic dynamics of Markov chains

Cites work

• scientific article; zbMATH DE number 3823893 (Why is no real title available?)
• scientific article; zbMATH DE number 1973372 (Why is no real title available?)
• scientific article; zbMATH DE number 5585443 (Why is no real title available?)
• A Logic of Probability with Decidable Model Checking
• A note on recurring series
• Approximate verification of the symbolic dynamics of Markov chains
• Deux propriétés décidables des suites récurrentes linéaires
• Einige Sätze über \(p\)-adische Potenzreihen mit Anwendung auf gewisse exponentielle Gleichungen.
• Generalized Automata and Stochastic Languages
• MDPs as distribution transformers: affine invariant synthesis for safety objectives
• Nonparametric statistics for stochastic processes
• On the positivity problem for simple linear recurrence sequences
• Positivity problems for low-order linear recurrence sequences
• Reachability problems for Markov chains
• Reprint: An arithmetic property of Taylor coefficients of rational functions (1935)
• Skolem meets schanuel
• Ultimate positivity is decidable for simple linear recurrence sequences

This page was built for publication: Skolem and positivity completeness of ergodic Markov chains

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