Model-Checking Discrete Duration Calculus

Duration calculus was introduced by Chaochen Zhou et al. (1991) as a logic to specify and reason about requirements for real-time systems. It is an extension of interval temporal logic where one can reason about integrated constraints over time-dependent and Boolean valued states without explicit mention of absolute time. Several major case studies have shown that duration calculus provides a high level of abstraction for both expressing and reasoning about specifications. Using timed automata one can express how real-time systems can be constructed at a level of detail which is close to an actual implementation. We consider in the paper the correctness of timed automata with respect to duration calculus formulae. For a subset of duration calculus, we show that one can automatically verify whether a timed automaton ℳ is correct with respect to a formula 𝒟, abbreviated ℳ|=𝒟, i.e. one can do model-checking. The subset we consider is expressive enough to formalize the requirements to the gas burner system given by A.P. Ravn (1993); but only for a discrete time domain. Model-checking is done by reducing the correctness problem ℳ|=𝒟 to the inclusion problem of regular languages