A Decision Method for Duration Calculus

Nathalie Chetcuti-Sperandio (Institut de Recherche en Informatique de Toulouse, France)

Luis Fariñas del Cerro (Institut de Recherche en Informatique de Toulouse, France)

Abstract: The Duration Calculus is an interval logic introduced for designing real-time systems. This calculus is able to capture important real-time problems like the specification of the behaviours of schedulers and classical examples like a gas burner. From a practical point of view an important challenge becomes to define automated proof procedures for this calculus. Since the propositional calculus is undecidable, we are interested then into isolating decidable fragments of this calculus. A first fragment was given and its decidability proved via regular languages. In this paper we isolate another fragment and we define a tableau method which gives a natural procedure to decide whether a given formula is satisfiable. This fragment is strong enough to embed Allen's Interval Algebra.

Keywords: Duration Calculus, automated deduction, tableau method

Categories: D.2.1, F.4.1, I.2.3, I.2.4