Publications
Publications › References ›
2001
Conference papers
Faster and Symbolic CTMC Model Checking
[KKNP01]
Joost-Pieter Katoen, Marta Kwiatkowska, Gethin Norman and David Parker.
Faster and Symbolic CTMC Model Checking.
In L. de Alfaro and S. Gilmore (editors), Proc. PAPM/PROBMIV'01, volume 2165 of Lecture Notes in Computer Science, pages 23-38, Springer.
September 2001.
ps.gz pdf bib
- Downloads
PostScript 113 KB
PDF 327 KB
BibTeX
- Notes
- The original publication is available at link.springer.com.
- Search for this paper
- Google · Google Scholar
Abstract
This paper reports on the implementation and the experiments with symbolic
model checking of continuous-time Markov chains using multi-terminal
binary decision diagrams (MTBDDs).
Properties are expressed in Continuous Stochastic Logic (CSL) [7]
which includes the means to express both transient and steady-state performance
measures.
We show that all CSL operators can be treated using standard operations
on MTBDDs, thus allowing a rather straightforward implementation of
symbolic CSL model checking on existing MTBDD-based platforms such as
the verifier PRISM.
The main result of the paper is an improvement of O(N) in the time
complexity of checking time-bounded until-formulas, where N is the number
of states in the CTMC under consideration.
This result yields a drastic speed-up in the verification time of model
checking CTMCs, both in the symbolic and non-symbolic case.