## Reachability problems for Markov chains

*S. Akshay*, *Timos Antonopoulos*,
*Joël
Ouaknine*, and *James Worrell*
We consider the following decision problem: given a finite Markov chain with
distinguished source and target states, and given a rational number *r*, does there
exist an integer *n* such that the probability to reach the target from the source
in *n* steps is *r*? This problem, which is not known to be decidable, lies at the
heart of many model checking questions on Markov chains. We provide evidence
of the hardness of the problem by giving a reduction from the Skolem Problem:
a number-theoretic decision problem whose decidability has been open for many
decades.

*Information Processing Letters* 115(2), 2015. 8 pages.

PDF
© 2015 Elsevier B.V.

Imprint / Data Protection