Model-checking for real-time systems
Rajeev Alur, Costas Courcoubetis, David L. Dill · Proceedings - Symposium on Logic in Computer Science · 2002
This research extends CTL model-checking to the analysis of real-time systems, whose correctness depends on the magnitudes of the timing delays. For specifications, the syntax of CTL is extended to allow quantitative temporal operators. The formulas of the resulting logic, TCTL, are interpretation over continuous computation trees, trees in which paths are maps from the set of nonnegative reals to system states. To model finite-state systems the notion of timed graphs is introduced-state-transition graphs extended with a mechanism that allows the expression of constant bounds on the delays between the state transition. As the main result, an algorithm is developed for model checking, that is, for determining the truth of a TCTL formula with respect to a timed graph. It is argued that choosing a dense domain, instead of a discrete domain, to model time does not blow up the complexity of the model-checking problem. On the negative side, it is shown that the denseness of the underlying time domain makes TCTL II/sub 1//sup 1/-hard. The question of deciding whether a given TCTL formula is implementable by a timed graph is also undecidable.>
Cited by 897 works. doi:10.1109/lics.1990.113766
Authors
References
- Introduction to automata theory, languages, and computation
- The temporal logic of programs
- Automatic verification of finite-state concurrent systems using temporal logic specifications
- Proving Liveness Properties of Concurrent Programs
- Automata for modeling real-time systems
- Safety analysis of timing properties in real-time systems
- Using branching time temporal logic to synthesize synchronization skeletons
- Timing assumptions and verification of finite-state concurrent systems
- Impartiality, justice and fairness: The ethics of concurrent termination
- A really temporal logic