On Generalized Interval Calculi

Gerard LigozatAAAI 1991

Introduction

In his 1991 paper, Gérard Ligozat established a foundational framework for temporal reasoning by generalizing James Allen’s Interval Algebra. While Allen's work focused on continuous intervals, Ligozat’s "Generalized Interval Calculus" provides a unified mathematical structure capable of handling points, non-convex intervals (sequences of segments), and mixed temporal objects.

The Problem: Beyond Allen's Interval Algebra

Temporal reasoning in AI traditionally relies on Allen’s Interval Algebra, which defines 13 basic relations between continuous "convex" intervals, such as before, meets, and overlaps. However, real-world applications often require reasoning about more complex temporal entities:

  1. Time points: Instantaneous events.
  2. Non-convex intervals: Discontinuous events, such as a recurring weekly meeting.
  3. Mixed objects: Relations between a point and an interval.

While previous extensions addressed specific cases, they lacked a unified theory. Ligozat sought to create a single algebraic and topological framework that subsumes these variations.

Methodology: $n$-intervals and $(p,q)$-relations

The paper utilizes Lattice Theory and Relation Algebra to build its framework. The core concept is the $n$-interval, defined as an ordered sequence of $n$ points on a timeline. In this view, Allen’s standard intervals are simply the special case where $n=2$.

Generalized intervals represented as sequences of points on a timeline.

To define the relationship between a $p$-interval and a $q$-interval, Ligozat introduces $(p,q)$-relations. These are determined by the "zones" created by the points of the second interval. Specifically, $q$ points divide the timeline into $2q+1$ distinct zones. The relation is then defined by the specific zone in which each point of the first interval resides.

A $q$-interval divides the timeline into $2q+1$ zones, used to define $(p,q)$-relations.

Key Insights: Topology and Convexity

Ligozat proves that the set of all possible relations between these intervals forms a distributive lattice. This mathematical structure captures the physical intuition of "moving an interval slightly." For instance, if an interval $i$ meets $j$, a slight rightward shift makes it overlap $j$. These transitions correspond to moving between adjacent nodes in a Hasse diagram.

A critical discovery is the identification of "interval" relations (or convex relations). These are relations describable by simple conjunctions of inequalities (e.g., $x_1 < y_1 \land x_2 > y_2$). Ligozat demonstrates that while general constraint satisfaction is NP-complete, restricting constraints to this "interval" subset allows standard constraint propagation algorithms to be complete and computationally efficient.

Key Results

The paper successfully unifies several disparate theories into a single framework of $(p,q)$-relations. Key mathematical results include:

  • Stability Theorem: The subset of "interval" relations remains stable under intersection, transposition, and composition.
  • Composition Formula: Ligozat provides a simplified explicit formula for composing two "interval" relations: $$[a, \beta] \circ [\gamma, \delta] = [\text{inf}(a \circ \gamma), \text{sup}(\beta \circ \delta)]$$ This formula replaces the need for massive, pre-computed transition tables for complex intervals.

Limitations and Future Work

Despite its elegance, the calculus assumes a linear time model and does not account for branching time or parallel futures. Additionally, the author notes that mapping real-world intervals to $n$-intervals can be semantically ambiguous—for example, a 3-interval could represent three points or a point and a segment. Finally, while the theoretical efficiency is proven, the paper does not include empirical software benchmarks.

Summary updated

BibTeX
@inproceedings{ligozat1991generalized,
  author = {Gerard Ligozat},
  title = {{On Generalized Interval Calculi}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure