On Generalized Interval Calculi

The calculus of time intervals defined by Allen has been extended in various ways in order to accomodate the need for considering other time objects than convex intervals (eg. time points and intervals, non convex intervals). This paper introduces and investigates the calculus of generalized intervals, which subsumes these extensions, in an algebraic setting. The set of (p, q)-relations, which generalizes the set of relations in the sense of Allen, has both an order structure and an algebraic structure. We show that, as an order, it is a distributive lattice whose properties express the topological properties of the set of (p, q)-relations. We also determine in what sense the algebraic operations of transposition and composition act continuously on this set. In Allen’ s algebra, the subset of relations which can be translated into conjunctive constraints on the endpoints using only c, >, =, 1, 2 has special computational significance (the constraint propagation algorithm is complete when restricted to such relations). We give a geometric characterization of a similar subset in the general case, and prove that it is stable under composition. As a consequence of this last fact, we get a very simple explicit formula for the composition of two elements in this subset. convenience of a language based on non convex intervals in such applications as the specification of concurrent processes. x -before y X. bepins y X. during y X &Q&Y 0 x. after y Fig. 1: some of Vilain’ s point-to-interval relations An interval in the sense of Allen is just a pair of ordered time points. A non convex interval (with a finite number of convex components) is entirely determined by the sequence of pairs associated to each convex component. This means that a non convex interval is an ordered sequence of an even number of time points. xl x2 x3 x4 X5 x6

Authors

• Gérard Ligozat

Keywords

No keywords are indexed for this paper.