Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10331878 | Information Processing Letters | 2015 | 4 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
S. Akshay, Timos Antonopoulos, Joël Ouaknine, James Worrell,