Allen Interval Calculus

Origin. Allen (1983). Interval relations. Qualitative time. Constraint reasoning. Foundation of temporal AI.

Models. Time intervals. Thirteen relations. Constraint networks. Composition tables. Qualitative reasoning.

Formalism.

Interval: I = [I⁻, I⁺] with I⁻ < I⁺. Start and end points. Non-zero duration.

Basic relations (13): I before J: I⁺ < J⁻. I meets J: I⁺ = J⁻. I overlaps J: I⁻ < J⁻ < I⁺ < J⁺. I starts J: I⁻ = J⁻, I⁺ < J⁺. I during J: J⁻ < I⁻, I⁺ < J⁺. I finishes J: I⁺ = J⁺, J⁻ < I⁻. I equals J: I⁻ = J⁻, I⁺ = J⁺. Plus 6 inverses: after, met-by, overlapped-by, started-by, contains, finished-by.

JEPD: Jointly exhaustive, pairwise disjoint. Exactly one basic relation holds. Complete and exclusive.

Disjunctive relations: R ⊆ {b, m, o, s, d, f, =, bi, mi, oi, si, di, fi}. Indefinite knowledge. R(I, J): one of R holds.

Composition: R₁ ∘ R₂ = {r₃ : ∃I,J,K. r₁(I,J) ∧ r₂(J,K) ∧ r₃(I,K)}. Composition table. Constraint propagation.

Constraint network: Variables = intervals. Constraints = relations. Path consistency. NP-complete general, tractable fragments.

Tractable subalgebras: ORD-Horn. Continuous endpoint. Pointisable.

Symbols.

Symbol	Unicode	Name	Meaning
b, m, o, s, d, f, =	—	Basic relations	Before, meets, overlaps, starts, during, finishes, equals
bi, mi, oi, si, di, fi	—	Converse relations	After, met-by, overlapped-by, started-by, contains, finished-by
∘	U+2218	Composition	Weak composition of two relations
[I⁻, I⁺]	—	Interval	Bounded by its start and end point
⁻	U+207B	Superscript minus	Left endpoint of an interval
⁺	U+207A	Superscript plus	Right endpoint of an interval
⊆	U+2286	Subset	A disjunctive relation is a set of basic ones
∃	U+2203	Exists	Intermediate interval in the composition clause
JEPD	—	Jointly exhaustive, pairwise disjoint	Exactly one basic relation holds of any pair

Metatheory. The thirteen basic relations of Allen (CACM 1983) are jointly exhaustive and pairwise disjoint over intervals on an unbounded dense linear order, so the 2¹³ disjunctions of them are closed under converse, intersection, and composition and form a relation algebra in Tarski's sense, shown representable by Ladkin and Maddux (1994). Deciding whether a network of such constraints is satisfiable is NP-complete (Vilain and Kautz 1986). Path consistency, computed by repeatedly replacing each constraint with its intersection against the composition of the other two, runs in O(n³) time and is sound but not complete: it removes some impossible labels but a path-consistent network can still be unsatisfiable. Nebel and Bürckert (JACM 1995) identified ORD-Horn as the unique maximal tractable subclass containing all thirteen basic relations, and Krokhin, Jeavons, and Jonsson (JACM 2003) completed the classification, showing there are exactly eighteen maximal tractable subalgebras and that every subalgebra not contained in one of them is NP-complete.

Applies to. Planning. Scheduling. Natural language. Temporal databases.

Limitations. The calculus is purely qualitative: it orders and nests intervals but assigns them no length, so "the meeting lasted two hours" and "the alarm sounded within five seconds" are not expressible, and the metric extensions that add them raise the complexity again. Intervals are convex and of nonzero duration, so points and non-convex occurrences such as "every Tuesday" have no representation. Tractability does not compose — the union of two tractable subalgebras is generally intractable — so a language must be chosen inside one of the eighteen maximal subalgebras and cannot be extended piecemeal. Path consistency is the feasible inference and it is incomplete, so deciding satisfiability in the full algebra still needs exponential backtracking. Constraints are binary throughout: no relation among three or more intervals is expressible, and a satisfiable network may admit exponentially many consistent scenarios that the algebra does not distinguish.