10 - Timed automata

Summary

The model of timed automata, introduced by Alur and Dill (1990, 1994), has by now established itself as a classical formalism for modelling real-time systems with a dense representation of time. The development of the timed-automata formalism was carried out largely in parallel with – and independently of – the work on timed extensions of process algebras. Roughly speaking, whereas the development of timed process algebras was driven by their (relative) expressiveness, their revealing of new behavioural equivalences and their axiomatizations, the development of the timed-automata formalism was largely driven by the goal of obtaining decidability results for several important properties (Dill, 1989). By now, real-time model checking tools such Uppaal (Behrmann, David and Larsen, 2004) and Kronos (Bozga et al., 1998) are based on the timed-automata formalism and on the substantial body of research on this model that has been targeted towards transforming the early decidability results into practically efficient algorithms.

Motivation

Timed automata are essentially nondeterministic finite automata equipped with a finite number of real-valued clocks, so that transitions can be conditioned on clock values and the performing of a particular transition can reset selected clocks. We shall now introduce the formalism intuitively, showing how the light switch from the start of the previous chapter can be described using the formalism of timed automata without recourse to assumptions such as the urgency of some actions or maximal progress. Graphically, we could model the light switch as in Figure 10.1.