Allen's interval algebra

Last updated November 06, 2024

Allen's interval algebra is a calculus for temporal reasoning that was introduced by James F. Allen in 1983.

Formal description

Relations

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

Relation	Illustration	Interpretation
$X\,{\mathrel {\mathbf {<} }}\,Y$ $Y\,{\mathrel {\mathbf {>} }}\,X$		X precedes Y Y is preceded by X
$X\,{\mathrel {\mathbf {m} }}\,Y$ $Y\,{\mathrel {\mathbf {mi} }}\,X$		X meets Y Y is met by X (i stands for inverse)
$X\,{\mathrel {\mathbf {o} }}\,Y$ $Y\,{\mathrel {\mathbf {oi} }}\,X$		X overlaps with Y Y is overlapped by X
$X\,{\mathrel {\mathbf {s} }}\,Y$ $Y\,{\mathrel {\mathbf {si} }}\,X$		X starts Y Y is started by X
$X\,{\mathrel {\mathbf {d} }}\,Y$ $Y\,{\mathrel {\mathbf {di} }}\,X$		X during Y Y contains X
$X\,{\mathrel {\mathbf {f} }}\,Y$ $Y\,{\mathrel {\mathbf {fi} }}\,X$		X finishes Y Y is finished by X
$X\,{\mathrel {\mathbf {=} }}\,Y$		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:

${\mbox{newspaper }}\mathbf {\{\operatorname {d} \}} {\mbox{ dinner}}$

${\mbox{dinner }}\mathbf {\{\operatorname {<} \}} {\mbox{ 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.

Composition of relations between intervals

For reasoning about the relations between temporal intervals, Allen's interval algebra provides a composition 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 operation, this turns Allen's interval algebra into a relation algebra.

For the example, one can infer ${\mbox{newspaper }}\mathbf {\{\operatorname {<} \}} {\mbox{ bed}}$ .

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

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

Related Research Articles

In mathematics, the absolute value or modulus of a real number $, denoted, is the non-negative value of without regard to its sign. Namely, if is a positive number, and if is negative, and . For example, the absolute value of 3 is 3, and the absolute value of -3 is also 3. The absolute value of a number may be thought of as its distance from zero.$

In mathematics, the associative property is a property of some binary operations that means that rearranging the parentheses in an expression will not change the result. In propositional logic, associativity is a valid rule of replacement for expressions in logical proofs.

In mathematics, a binary relation associates elements of one set called the domain with elements of another set called the codomain. Precisely, a binary relation over sets $and is a set of ordered pairs where is in and is in . It encodes the common concept of relation: an element is related to an element, if and only if the pair belongs to the set of ordered pairs that defines the binary relation.$

In mathematics, an operator is generally a mapping or function that acts on elements of a space to produce elements of another space. There is no general definition of an operator, but the term is often used in place of function when the domain is a set of functions or other structured objects. Also, the domain of an operator is often difficult to characterize explicitly, and may be extended so as to act on related objects.

In mathematics, the polar coordinate system is a two-dimensional coordinate system in which each point on a plane is determined by a distance from a reference point and an angle from a reference direction. The reference point is called the pole, and the ray from the pole in the reference direction is the polar axis. The distance from the pole is called the radial coordinate, radial distance or simply radius, and the angle is called the angular coordinate, polar angle, or azimuth. Angles in polar notation are generally expressed in either degrees or radians.

The Cauchy–Schwarz inequality is an upper bound on the inner product between two vectors in an inner product space in terms of the product of the vector norms. It is considered one of the most important and widely used inequalities in mathematics.

In linear algebra, the trace of a square matrix $A$ , denoted $tr(A)$ , is the sum of the elements on its main diagonal, $. It is only defined for a square matrix.$

Del, or nabla, is an operator used in mathematics as a vector differential operator, usually represented by the nabla symbol ∇. When applied to a function defined on a one-dimensional domain, it denotes the standard derivative of the function as defined in calculus. When applied to a field, it may denote any one of three operations depending on the way it is applied: the gradient or (locally) steepest slope of a scalar field ; the divergence of a vector field; or the curl (rotation) of a vector field.

<span class="mw-page-title-main">Transpose</span> Matrix operation which flips a matrix over its diagonal

In linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal; that is, it switches the row and column indices of the matrix $A$ by producing another matrix, often denoted by $A T$ .

Description logics (DL) are a family of formal knowledge representation languages. Many DLs are more expressive than propositional logic but less expressive than first-order logic. In contrast to the latter, the core reasoning problems for DLs are (usually) decidable, and efficient decision procedures have been designed and implemented for these problems. There are general, spatial, temporal, spatiotemporal, and fuzzy description logics, and each description logic features a different balance between expressive power and reasoning complexity by supporting different sets of mathematical constructors.

In mathematics, a function from a set $X$ to a set $Y$ assigns to each element of $X$ exactly one element of $Y$ . The set $X$ is called the domain of the function and the set $Y$ is called the codomain of the function.

<span class="mw-page-title-main">Cone (topology)</span>

In topology, especially algebraic topology, the coneof a topological space $is intuitively obtained by stretching X into a cylinder and then collapsing one of its end faces to a point. The cone of X is denoted by or by .$

In mathematics, the kernel of a linear map, also known as the null space or nullspace, is the part of the domain which is mapped to the zero vector of the co-domain; the kernel is always a linear subspace of the domain. That is, given a linear map $L : V \to W$ between two vector spaces $V$ and $W$ , the kernel of $L$ is the vector space of all elements $v$ of $V$ such that $L (v) = 0$ , where $0$ denotes the zero vector in $W$ , or more symbolically:

In formal ontology, a branch of metaphysics, and in ontological computer science, mereotopology is a first-order theory, embodying mereological and topological concepts, of the relations among wholes, parts, parts of parts, and the boundaries between parts.

In differential geometry, the four-gradient $is the four-vector analogue of the gradient from vector calculus.$

Spatial–temporal reasoning is an area of artificial intelligence that draws from the fields of computer science, cognitive science, and cognitive psychology. The theoretic goal—on the cognitive side—involves representing and reasoning spatial-temporal knowledge in mind. The applied goal—on the computing side—involves developing high-level control systems of automata for navigating and understanding time and space.

In mathematics, the converse of a binary relation is the relation that occurs when the order of the elements is switched in the relation. For example, the converse of the relation 'child of' is the relation 'parent of'. In formal terms, if $and are sets and is a relation from to then is the relation defined so that if and only if In set-builder notation,$

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 on a set X, that is, subsets of the cartesian square X², with R•S interpreted as the usual composition of binary relations R and S, and with the converse of R as the converse relation.

In special relativity, the classical concept of velocity is converted to rapidity to accommodate the limit determined by the speed of light. Velocities must be combined by Einstein's velocity-addition formula. For low speeds, rapidity and velocity are almost exactly proportional but, for higher velocities, rapidity takes a larger value, with the rapidity of light being infinite.

<span class="mw-page-title-main">Region connection calculus</span>

The region connection calculus (RCC) is intended to serve for qualitative spatial representation and reasoning. RCC abstractly describes regions by their possible relations to each other. RCC8 consists of 8 basic relations that are possible between two regions:

References

↑ 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

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.

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[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

[1]