Allen's Interval Algebra

The algebra defines a complete set of jointly exhaustive and pairwise disjoint (JEPD) relations: Before, Meets, Overlaps, Starts, During, Finishes, and their inverses (After, MetBy, OverlappedBy, StartedBy, Contains, FinishedBy), plus Equals. These 13 relations form an atomic relation set where any two definite intervals must satisfy exactly one relation.

The algebra's deductive power comes from its transitivity table, a 13x13 matrix defining the composition of relations. For example, if interval A is Before interval B, and B Contains interval C, the table infers that A is Before C. This enables constraint propagation across a network of temporal intervals to detect inconsistencies or deduce new, implicit relationships.

When temporal knowledge is incomplete, a constraint between two intervals is expressed as a disjunction of base relations, e.g., {Before, Meets}. The algebra operates on these sets using set-theoretic composition. A path consistency algorithm iteratively refines these disjunctive constraints by intersecting compositions along all paths in the network until a fixed point is reached or an inconsistency (empty set) is found.

The algebra can be extended to handle points (instants) by treating a point as an interval with zero duration where the start equals the end. This allows reasoning about deadlines and instantaneous events within the same framework. A point can be Before, Meets, or MetBy an interval, but cannot Overlap or Contain it, reducing the applicable relation set for point-interval constraints.

The 13 relations are organized into a conceptual neighborhood graph that defines which relations are continuous transformations of one another. For instance, Before can transition to Meets by decreasing the gap between intervals, and Meets can transition to Overlaps by moving the intervals closer. This structure is critical for modeling temporal uncertainty and reasoning about events with imprecise boundaries.

Determining the consistency of a network of Allen relations is an NP-complete problem in the general case when disjunctions are allowed. However, restricting constraints to the ORD-Horn subclass—a set of 868 tractable relations—enables polynomial-time reasoning using path consistency. This tractable subset is sufficient for most practical legal temporal constraint problems.

A formal system for reasoning about propositions qualified in terms of time. While Allen's algebra handles qualitative interval relations, temporal logic introduces modal operators like 'always' (□), 'eventually' (◇), and 'until' (U) to express propositions over linear or branching time. In contract analysis, Linear Temporal Logic (LTL) can specify rules such as 'a payment obligation must eventually be fulfilled before the sunset clause always terminates the agreement.'

The algorithmic process of finding a valid timeline that satisfies all extracted temporal constraints. Given a set of intervals and their Allen relations (e.g., 'Payment Period meets Grace Period', 'Notice before Termination'), a constraint solver propagates these to detect inconsistencies and compute feasible schedules. This is the core engine that validates whether a contract's deadlines are logically coherent.

A directed graph where nodes represent contractual events or deadlines and edges represent temporal precedence constraints derived from Allen relations. For example, a 'before' relation creates a strict precedence edge. This structure enables critical path analysis across multi-document agreements, identifying the chain of obligations that determines the overall transaction timeline.

A logical inconsistency between temporal statements in one or more contracts. Allen's algebra provides a formal framework for detecting these conflicts. For instance, if Clause A states 'Inspection occurs during Construction' and Clause B states 'Inspection occurs after Construction', the system identifies a contradiction because an interval cannot simultaneously satisfy both during and after relations with the same reference interval.

A W3C ontology providing a standard vocabulary for describing instants, intervals, and their relationships in knowledge graphs. OWL-Time directly implements Allen's thirteen interval relations as object properties (e.g., time:intervalBefore, time:intervalMeets), enabling semantic reasoning engines to infer new temporal facts and check consistency across contract knowledge bases using standardized description logic.

A method of analyzing streaming events to identify meaningful patterns in real-time. CEP engines use Allen-like temporal operators to define patterns such as 'a missed payment event followed by a cure period expiration without a payment received event triggers a default.' This bridges the gap between static contract analysis and dynamic obligation monitoring in live systems.