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₃ : ∃J. 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.

Metatheory. Relation algebra. Composition tables. Tractability. Constraint satisfaction.

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

Limitations. Qualitative only. NP-complete general. No metric. Point vs interval debates.

© 2026 Lingenic LLC