Allen's interval algebra is a calculus for temporal reasoning that was introduced by James F. Allen in 1983.
The calculus defines possible relations between time intervals and provides a composition table that can be used as a basisfor reasoning about temporal descriptions of events.
The following 13 base relations capture the possible relations between two intervals.
| Relation !Illustration | Interpretation | - | Xl{< Yl{> | X precedes YY is preceded by X | - | Xl{m Yl{mi | X meets YY is met by X (i stands for inverse) | - | Xl{o Yl{oi | X overlaps with YY is overlapped by X | - | Xl{s Yl{si | X starts YY is started by X | - | Xl{d Yl{di | X during YY contains X | - | Xl{f Yl{fi | X finishes YY is finished by X | - | Xl{= | X is equal to Y |
|---|
The sentences
During dinner, Peter reads the newspaper. Afterwards, he goes to bed.are formalized in Allen's Interval Algebra as follows:
newspaper\{\operatorname{d\}}dinner
dinner\{\operatorname{<\}}bed
In general, the number of different relations between n intervals, starting with n = 0, is 1, 1, 13, 409, 23917, 2244361... OEIS A055203. The special case shown above is for n = 2.
For reasoning about the relations between temporal intervals, Allen's interval algebra provides a composition table. Given the relation between
X
Y
Y
Z
X
Z
For the example, one can infer
newspaper\{\operatorname{<\}}bed
Allen's interval algebra can be used for the description of both temporal intervals and spatial configurations. For the latter use, the relations are interpreted as describing the relative position of spatial objects. This also works for three-dimensional objects by listing the relation for each coordinate separately.
The study of overlapping markup uses a similar algebra (see [1]). Its models have more variations depending on whether endpoints of document structures are permitted to be truly co-located, or merely [tangent].