2009 · 76 citations · 14 references
ComputingComputer ScienceMathematicsModel-based Systems EngineeringReal-time SystemsSystems ModelingAutomata TheoryFinite AutomataMarkov ChainsMarkov ProcessesModel CheckingReal-time Systems DesignContinuous-time Markov ChainsContinuous-time Markov ProcessesPiecewise Deterministic Markov ProcessesReachabilityReachability AnalysisReal-time Systems VerificationTimed AutomataTimed Model Checking
We study the following problem: given a continuous-time Markov chain (CTMC) C, and a linear real-time property provided as a deterministic timed automaton (DTA) A, what is the probability of the set of paths of C that are accepted by A (C satisfies A)? It is shown that this set of paths is measurable and computing its probability can be reduced to computing the reachability probability in a piecewise deterministic Markov process (PDP). The reachability probability is characterized as the least solution of a system of integral equations and is shown to be approximated by solving a system of partial differential equations. For the special case of single-clock DTA, the system of integral equations can be transformed into a system of linear equations where the coefficients are solutions of ordinary differential equations.
14
Rajeev Alur, David L. Dill · Theoretical Computer Science · 1994 · 6.5K citations
Mathematical Methods for Physicists
George B. Arfken, Jon Mathews · American Journal of Physics · 1972 · 4.1K citations
Automatic verification of probabilistic concurrent finite state programs
Moshe Y. Vardi · 1985 · 675 citations
Model-checking continuous-time Markov chains
Adnan Aziz, Kumud Sanwal, Vigyan Singhal et al. · ACM Transactions on Computational Logic · 2000 · 415 citations