On Generalized Interval Calculi

Gérard Ligozat

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 <, >,=, <_,>_ 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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.