Allen's interval algebra

Last updated

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

Contents

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.

Relation Illustration Interpretation

Allen calculus before.png X precedes Y

Y is preceded by X

Allen calculus meet.png X meets Y

Y is met by X (i stands for inverse)

Allen calculus overlap.png X overlaps with Y

Y is overlapped by X

Allen calculus start.png X starts Y

Y is started by X

Allen calculus during.png X during Y

Y contains X

Allen calculus finish.png X finishes Y

Y is finished by X

Allen calculus equal.png 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

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

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

See also

Related Research Articles

<span class="mw-page-title-main">Absolute value</span> Distance from zero to a number

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.

<span class="mw-page-title-main">Associative property</span> Property of a mathematical operation

In mathematics, the associative property is a property of some binary operations, which 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. A binary relation over sets X and Y is a set of ordered pairs (x, y) consisting of elements x from X and y from Y. It is a generalization of the more widely understood idea of a unary function. It encodes the common concept of relation: an element x is related to an element y, if and only if the pair (x, y) belongs to the set of ordered pairs that defines the binary relation. A binary relation is the most studied special case n = 2 of an n-ary relation over sets X1, ..., Xn, which is a subset of the Cartesian product

<span class="mw-page-title-main">Isomorphism</span> In mathematics, invertible homomorphism

In mathematics, an isomorphism is a structure-preserving mapping between two structures of the same type that can be reversed by an inverse mapping. Two mathematical structures are isomorphic if an isomorphism exists between them. The word isomorphism is derived from the Ancient Greek: ἴσοςisos "equal", and μορφήmorphe "form" or "shape".

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. See Operator (physics) for other examples.

<span class="mw-page-title-main">Polar coordinate system</span> Coordinates comprising a distance and an angle

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 defined to be the sum of elements on the main diagonal of A. The trace is only defined for a square matrix.

In mathematics, a Clifford algebra is an algebra generated by a vector space with a quadratic form, and is a unital associative algebra with the additonal structure of a distinguished subspace. As K-algebras, they generalize the real numbers, complex numbers, quaternions and several other hypercomplex number systems. The theory of Clifford algebras is intimately connected with the theory of quadratic forms and orthogonal transformations. Clifford algebras have important applications in a variety of fields including geometry, theoretical physics and digital image processing. They are named after the English mathematician William Kingdon Clifford (1845–1879).

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

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 logic, philosophy and related fields, mereology is the study of parts and the wholes they form. Whereas set theory is founded on the membership relation between a set and its elements, mereology emphasizes the meronomic relation between entities, which—from a set-theoretic perspective—is closer to the concept of inclusion between sets.

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,

A logical matrix, binary matrix, relation matrix, Boolean matrix, or (0, 1)-matrix is a matrix with entries from the Boolean domain B = {0, 1}. Such a matrix can be used to represent a binary relation between a pair of finite sets. It is an important tool in combinatorial mathematics and theoretical computer science.

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

<span class="mw-page-title-main">Corner detection</span> Approach used in computer vision systems

Corner detection is an approach used within computer vision systems to extract certain kinds of features and infer the contents of an image. Corner detection is frequently used in motion detection, image registration, video tracking, image mosaicing, panorama stitching, 3D reconstruction and object recognition. Corner detection overlaps with the topic of interest point detection.

<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

  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