Abstract
This paper makes verifying continuous-time Markov chains (CTMCs) against deterministic timed automata (DTA) objectives practical. We show that verifying 1-clock DTA can be done by analyzing subgraphs of the product of CTMC C and the region graph of DTA A. This improves upon earlier results and allows to only use standard analysis algorithms. Our graph decomposition approach naturally enables bisimulation minimization as well as parallelization. Experiments with various examples confirm that these optimizations lead to significant speed-ups. We also report on experiments with multiple-clock DTA objectives. The objectives and the size of the problem instances that can be checked with our prototypical tool go (far) beyond what could be checked so far.
Original language | Undefined |
---|---|
Pages | 128-142 |
Number of pages | 15 |
DOIs | |
Publication status | Published - Mar 2011 |
Event | 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2011 - Saarbrücken, Germany Duration: 26 Mar 2011 → 3 Apr 2011 |
Conference
Conference | 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, TACAS 2011 |
---|---|
Period | 26/03/11 → 3/04/11 |
Other | 26 March - 3 April 2011 |
Keywords
- IR-79389
- EWI-21247