2010 · 41 citations · 14 references
ComputingComputer ScienceFormal MethodsModel-based Systems EngineeringSystems ModelingConcurrency VerificationDeductive VerificationFinite State Machine ModelingModel CheckingVerificationAbstract Model CheckingProbabilistic Model Checking
Discrete-Time Markov Chains (DTMCs) are a widely-used formalism to model probabilistic systems. On the one hand, available tools like PRISM or MRMC offer efficient model checking algorithms and thus support the verification of DTMCs. However, these algorithms do not provide any diagnostic information in the form of counterexamples, which are highly important for the correction of erroneous systems. On the other hand, there exist several approaches to generate counterexamples for DTMCs, but all these approaches require the model checking result for completeness. In this paper we introduce a model checking algorithm for DTMCs that also supports the generation of counterexamples. Our algorithm, based on the detection and abstraction of strongly connected components, offers abstract counterexamples, which can be interactively refined by the user.
14
Depth-First Search and Linear Graph Algorithms
Robert E. Tarjan · SIAM Journal on Computing · 1972 · 6K citations
Michael K. Reiter, Aviel D. Rubin · ACM Transactions on Information and System Security · 1998 · 1.8K citations
A logic for reasoning about time and reliability
Hans Hansson, Bengt Jönsson · Formal Aspects of Computing · 1994 · 1.4K citations · Full text
The ins and outs of the probabilistic model checker MRMC
Joost-Pieter Katoen, Ivan S. Zapreev, Ernst Moritz Hahn et al. · Performance Evaluation · 2010 · 250 citations