DOI: 10.3724/SP.J.1016.2013.02587

Chinese Journal of Computers (计算机学报) 2013/36:12 PP.2587-2600

Bounded Model Checking for Markov Decision Processes

Bounded model checking has been proven to be a powerful technique for the verification of reactive systems, since it can avoid the space blow up of BDDs(Binary Decision Diagrams). To avoid the space blow up of MTBDDs(Multi Terminal Binary Decision Diagrams), a bounded model checking technique for Markov decision processes is proposed. The biggest feature of Markov decision processes is able to describe the nondeterministic choice. For this feature, the bounded semantics of the probabilistic computation tree logic is first presented, and its correctness is proven. Second, based on the evolution trend of the sequence consisting of probability measure calculated by the bounded model checking procedure,three termination criterions are given. Third, the bounded model checking procedure of the probabilistic computation tree logic is transformed into a linear equation. Finally, the experiment results show that compared with the unbounded model checking if the length of the witness is short then the bounded model checking needs less space.

Key words:model checking,bounded model checking,probabilistic computation tree logic,Markov decision processes,state space explosion

ReleaseDate:2014-07-21 17:04:09