Decisive Markov Chains

Details Decisive Markov Chains Decisive Markov Chains

2007-06-18

arxiv.org/abs/0706.2585v2

LMCS 3 (4:7) 2007

Computer Science

Logic in Computer Science

32 pages, 0 figures

Scientific paper

10.2168/LMCS-3(4:7)2007

We consider qualitative and quantitative verification problems for infinite-state Markov chains. We call a Markov chain decisive w.r.t. a given set of target states F if it almost certainly eventually reaches either F or a state from which F can no longer be reached. While all finite Markov chains are trivially decisive (for every set F), this also holds for many classes of infinite Markov chains. Infinite Markov chains which contain a finite attractor are decisive w.r.t. every set F. In particular, this holds for probabilistic lossy channel systems (PLCS). Furthermore, all globally coarse Markov chains are decisive. This class includes probabilistic vector addition systems (PVASS) and probabilistic noisy Turing machines (PNTM). We consider both safety and liveness problems for decisive Markov chains, i.e., the probabilities that a given set of states F is eventually reached or reached infinitely often, respectively. 1. We express the qualitative problems in abstract terms for decisive Markov chains, and show an almost complete picture of its decidability for PLCS, PVASS and PNTM. 2. We also show that the path enumeration algorithm of Iyer and Narasimha terminates for decisive Markov chains and can thus be used to solve the approximate quantitative safety problem. A modified variant of this algorithm solves the approximate quantitative liveness problem. 3. Finally, we show that the exact probability of (repeatedly) reaching F cannot be effectively expressed (in a uniform way) in Tarski-algebra for either PLCS, PVASS or (P)NTM.

Affiliated with

Also associated with

No associations

Rating

Decisive Markov Chains does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Decisive Markov Chains, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Decisive Markov Chains will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-609836