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.
The following 13 base relations capture the possible relations between two intervals.
To see that the 13 relations are exhaustive, note that each point of can be at 5 possible locations relative to : before, at the start, within, at the end, after. These give possible relative positions for the start and the end of . Of these, we cannot have since , and similarly we cannot have , thus giving us 13 possible relations.
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 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.
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
are formalized in Allen's Interval Algebra as follows:
For the example, one can infer .
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].
In the cultural heritage ontology CIDOC CRM, Allen relations are replaced by so-called temporal primitives, which facilitate the formulation of attestable statements as well as reasoning about these statements. [2] Temporal primitives split up the Allen relations into individual statements about the start or end of the intervals. For example, X overlaps with Y () can be split as follows:
In addition, the equal to of the Allen relations is replaced by before or with and after or with. A simple example:
In the example, it is not necessary to specify whether Harold II was killed at the beginning or during or at the end of the battle, i.e. whether , or applies (disjunctions such as cannot be expressed in CIDOC CRM, except in queries). If it is relevant for a particular historical question, it can be specified later by adding e.g. ends after the start of.
CIDOC CRM distinguishes between events and their corresponding time intervals. Allen relations and temporal primitives are statements between events and only as a consequence between their time intervals. Another difference is that temporal, spatial and spatiotemporal entities in CIDOC CRM are seen as having fuzzy borders. Especially statements about exact simultaneity are otherwise extremely rare.
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, the derivative is a fundamental tool that quantifies the sensitivity to change of a function's output with respect to its input. The derivative of a function of a single variable at a chosen input value, when it exists, is the slope of the tangent line to the graph of the function at that point. The tangent line is the best linear approximation of the function near that input value. For this reason, the derivative is often described as the instantaneous rate of change, the ratio of the instantaneous change in the dependent variable to that of the independent variable. The process of finding a derivative is called differentiation.
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.
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.
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.
In mathematics, the name symplectic group can refer to two different, but closely related, collections of mathematical groups, denoted Sp(2n, F) and Sp(n) for positive integer n and field F (usually C or R). The latter is called the compact symplectic group and is also denoted by . Many authors prefer slightly different notations, usually differing by factors of 2. The notation used here is consistent with the size of the most common matrices which represent the groups. In Cartan's classification of the simple Lie algebras, the Lie algebra of the complex group Sp(2n, C) is denoted Cn, and Sp(n) is the compact real form of Sp(2n, C). Note that when we refer to the (compact) symplectic group it is implied that we are talking about the collection of (compact) symplectic groups, indexed by their dimension n.
In mathematics, particularly in linear algebra, a skew-symmetricmatrix is a square matrix whose transpose equals its negative. That is, it satisfies the condition
In mathematics, the exterior algebra or Grassmann algebra of a vector space is an associative algebra that contains which has a product, called exterior product or wedge product and denoted with , such that for every vector in The exterior algebra is named after Hermann Grassmann, and the names of the product come from the "wedge" symbol and the fact that the product of two elements of is "outside"
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 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 mathematics, matrix calculus is a specialized notation for doing multivariable calculus, especially over spaces of matrices. It collects the various partial derivatives of a single function with respect to many variables, and/or of a multivariate function with respect to a single variable, into vectors and matrices that can be treated as single entities. This greatly simplifies operations such as finding the maximum or minimum of a multivariate function and solving systems of differential equations. The notation used here is commonly used in statistics and engineering, while the tensor index notation is preferred in physics.
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 2 X 2 of all binary relations on a set X, that is, subsets of the cartesian square X2, 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.
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.
In mathematics, near sets are either spatially close or descriptively close. Spatially close sets have nonempty intersection. In other words, spatially close sets are not disjoint sets, since they always have at least one element in common. Descriptively close sets contain elements that have matching descriptions. Such sets can be either disjoint or non-disjoint sets. Spatially near sets are also descriptively near sets.