FLOC 2018: FEDERATED LOGIC CONFERENCE 2018
Monitoring CTMCs By Multi-Clock Timed Automata

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: