Record Details

Reachability problems for Markov chains

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Reachability problems for Markov chains
 
Creator AKSHAY, S
ANTONOPOULOS, T
OUAKNINE, J
WORRELL, J
 
Subject AUTOMATA
Formal methods
Skolem problem
Positivity problem
Probabilistic model checking
Markov chains
 
Description 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. (C) 2014 Elsevier B.V. All rights reserved.
 
Publisher ELSEVIER SCIENCE BV
 
Date 2016-01-14T14:07:05Z
2016-01-14T14:07:05Z
2015
 
Type Article
 
Identifier INFORMATION PROCESSING LETTERS, 115(2)155-158
0020-0190
1872-6119
http://dx.doi.org/10.1016/j.ipl.2014.08.013
http://dspace.library.iitb.ac.in/jspui/handle/100/17686
 
Language en