Allen's interval algebra

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 basis for reasoning about temporal descriptions of events.

Formal description

edit

Relations

edit

The following 13 base relations capture the possible relations between two intervals.

Relation Illustration Interpretation
 

 

  X precedes Y

Y is preceded by X

 

 

  X meets Y

Y is met by X (i stands for inverse)

 

 

  X overlaps with Y

Y is overlapped by X

 

 

  X starts Y

Y is started by X

 

 

  X during Y

Y contains X

 

 

  X finishes Y

Y is finished by X

    X is equal to Y

Using this calculus, given facts can be formalized and then used for automatic reasoning. Relations between intervals are formalized as sets of base relations.

The sentences

During dinner, Peter reads the newspaper. Afterwards, he goes to bed.

are formalized in Allen's Interval Algebra as follows:

 

 

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.

Composition of relations between intervals

edit

For reasoning about the relations between temporal intervals, Allen's interval algebra provides a composition table. Given the relation between   and   and the relation between   and  , the composition table allows for concluding about the relation between   and  . Together with a converse operation, this turns Allen's interval algebra into a relation algebra.

For the example, one can infer  .

Extensions

edit

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].

Implementations

edit

See also

edit

References

edit
  1. ^ Steven DeRose. Markup Overlap: A Review and a Horse. In Proceedings of Extreme Markup Languages 2004, Montréal, Québec, August 2-6, 2004. http://xml.coverpages.org/DeRoseEML2004.pdf

Sources

edit
  • Allen, James F. (26 November 1983). "Maintaining knowledge about temporal intervals" (PDF). Communications of the ACM. 26 (11): 832–843. CiteSeerX 10.1.1.472.5244. doi:10.1145/182.358434. hdl:1802/10574. ISSN 0001-0782. S2CID 16729000.
  • Nebel, Bernhard; Bürckert, Hans-Jürgen (1995). "Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra" (PDF). Journal of the ACM. 42: 43–66. doi:10.1145/200836.200848. S2CID 6586759.
  • van Beek, Peter; Manchak, Dennis W. (1996). "The design and experimental analysis of algorithms for temporal reasoning" (PDF). Journal of Artificial Intelligence Research. 4 (1996): 1–18. arXiv:cs/9601101. Bibcode:1996cs........1101V. doi:10.1613/jair.232. S2CID 3204600. Archived from the original (PDF) on 6 July 2017. Retrieved 6 May 2017.