''For the type of boolean algebra called interval algebra, see

Boolean algebra (structure) In abstract algebra, a Boolean algebra or Boolean lattice is a complemented distributive lattice. This type of algebraic structure captures essential properties of both set operations and logic operations. A Boolean algebra can be seen as a gen ...

'' Allen's interval algebra is a

calculus Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizations of arithm ...

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

Relations

The following 13 base relations capture the possible relations between two intervals. 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 sentence : ''During dinner, Peter reads the newspaper. Afterwards, he goes to bed.'' is formalized in Allen's Interval Algebra as follows:

\mbox \mathbf \mbox

\mbox \mathbf \mbox

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

For reasoning about the relations between temporal intervals, Allen's interval algebra provides a

composition Composition or Compositions may refer to: Arts and literature *Composition (dance), practice and teaching of choreography *Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include v ...

table. Given the relation between

X

and

Y

and the relation between

Y

and

Z

, the composition table allows for concluding about the relation between

X

and

Z

. Together with a

converse Converse may refer to: Mathematics and logic * Converse (logic), the result of reversing the two parts of a definite or implicational statement ** Converse implication, the converse of a material implication ** Converse nonimplication, a logical c ...

operation, this turns Allen's interval algebra into a

relation algebra In mathematics and abstract algebra, a relation algebra is a residuated Boolean algebra expanded with an involution called converse, a unary operation. The motivating example of a relation algebra is the algebra 2''X''² of all binary relations ...

. For the example, one can infer

\mbox \mathbf \mbox

Extensions

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 In markup languages and the digital humanities, overlap occurs when a document has two or more structures that interact in a non-hierarchical manner. A document with overlapping markup cannot be represented as a tree. This is also known as concurre ...

uses a similar algebra (see 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). Its models have more variations depending on whether endpoints of document structures are permitted to be truly co-located, or merely angent

Implementations

A simple java library implementing the concept of Allen's temporal relations and the path consistency algorithm

Java library implementing Allen's Interval Algebra
(incl. data and index structures, e.g.,

interval_tree In computer science, an interval tree is a tree data structure to hold intervals. Specifically, it allows one to efficiently find all intervals that overlap with any given interval or point. It is often used for windowing queries, for instance, to f ...

)
OWL-Time Time Ontology in OWL
an OWL-2 DL ontology of temporal concepts, for describing the temporal properties of resources in the world or described in Web pages.
GQR
is a reasoner for Allen's interval algebra (and many others)
qualreas
is a Python framework for qualitative reasoning over networks of relation algebras, such as RCC-8, Allen's interval algebra, and Allen's algebra integrated with Time Points and situated in either Left- or Right-Branching Time.
SparQ
is a reasoner for Allen's interval algebra (and many others)
EveXL
is a small domain-specific language for the detection of events that implements the Interval Algebra's operators via ASCII art patterns.

References

Sources

* * * {{cite journal , first1=Peter , last1=van Beek , first2=Dennis W. , last2=Manchak , title=The design and experimental analysis of algorithms for temporal reasoning , url=https://www.jair.org/media/232/live-232-1507-jair.pdf , journal=Journal of Artificial Intelligence Research , volume=4 , issue=1996 , pages=1–18 , date=1996 , bibcode=1996cs........1101V , arxiv=cs/9601101 , doi=10.1613/jair.232 , s2cid=3204600 , access-date=6 May 2017 , archive-date=6 July 2017 , archive-url=https://web.archive.org/web/20170706031711/http://jair.org/media/232/live-232-1507-jair.pdf , url-status=dead Knowledge representation Constraint programming