Generation of Counterexamples for Model Checking of Markov Decision Processes

Date Added: Jul 2009
Format: PDF

The practical usefulness of a model checker as a debugging tool relies on its ability to provide diagnostic information, sometimes also referred to as a counterexample. Current stochastic model checkers do not provide such diagnostic information. In this paper, the authors address this problem for Markov Decision Processes. First, they define the notion of counterexamples in this context. Then, they discuss three methods to generate informative counterexamples which are helpful in system debugging. They point out the advantages and drawbacks of each method. They also experimentally compare all three methods. Their experiments demonstrate the conditions under which each method is appropriate to be used.