Faster and symbolic CTMC model checking


Share/Save/Bookmark

Katoen, Joost-Pieter and Kwiatkowska, Marta and Norman, Gethin and Parker, David (2001) Faster and symbolic CTMC model checking. In: Joint International Workshop on Process Algebra and Probabilistic Methods & Performance Modeling and Verification, PAPM-PROBMIV 2001, September 12-14, 2001, Aachen, Germany (pp. pp. 23-38).

[img] PDF
Restricted to UT campus only
: Request a copy
317kB
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.
Item Type:Conference or Workshop Item
Copyright:© 2001 Springer
Faculty:
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/63281
Official URL:http://dx.doi.org/10.1007/3-540-44804-7_2
Export this item as:BibTeX
EndNote
HTML Citation
Reference Manager

 

Repository Staff Only: item control page

Metis ID: 203851