Authors: Yijun Feng, Joost-Pieter Katoen, Haokun Li, Bican Xia and Naijun Zhan
Paper Information
Title: | Monitoring CTMCs By Multi-Clock Timed Automata |
Authors: | Yijun Feng, Joost-Pieter Katoen, Haokun Li, Bican Xia and Naijun Zhan |
Proceedings: | CAV All Papers |
Editors: | Georg Weissenbacher, Hana Chockler and Igor Konnov |
Keywords: | Model checking, Continuous-time Markov chain, Multi-clock timed automata, Ordinary differential equation |
Abstract: | ABSTRACT. This paper presents a numerical algorithm to verify continuous-time Markov chains (CTMCs) against multi-clock deterministic timed automata (DTA). These DTA allow for specifying properties that cannot be expressed in CSL, the logic for CTMCs used by state-of-the-art probabilistic model checkers. The core problem is to compute the probability of timed runs by the CTMC ${\cal C}$ that are accepted by the DTA ${\cal A}$. These likelihoods equal reachability probabilities in an embedded piecewise deterministic Markov process (EPDP) obtained as product ofn${\cal C}$ and ${\cal A}$'s region automaton. This paper provides a numerical algorithm to efficiently solve the PDEs describing these reachability probabilities. The key insight is to solve an ordinary differential equation (ODE) that exploits the specific characteristics of the product EPDP. We provide the numerical precision of our algorithm and present experimental results with a prototypical implementation. |
Pages: | 18 |
Talk: | Jul 15 11:45 (Session 103A: Runtime Verification, Hybrid and Timed Systems) |
Paper: |