Allen calculus

The Allen calculus , also known as Allen's interval algebra, is a logic for the representation of temporal relationships and for logical reasoning, which was introduced in 1983 by James F. Allen .

The calculus defines possible temporal relationships between intervals and describes an algorithm to be able to draw conclusions between them based on temporal descriptions of events.

Formal description

Relations

With the help of the 13 relationships shown, it is possible to describe all possible relationships between exactly two intervals. The relations also include the inverses.

relation	illustration	interpretation
${\displaystyle X\mathbf {\operatorname {<} } Y}$ ${\displaystyle Y\mathbf {\operatorname {>} } X}$		X takes place before Y.
${\displaystyle X\mathbf {\operatorname {m} } Y}$ ${\displaystyle Y\mathbf {\operatorname {mi} } X}$		X meets Y (English X m eets Y , the i stands for i nverse )
${\displaystyle X\mathbf {\operatorname {o} } Y}$ ${\displaystyle Y\mathbf {\operatorname {oi} } X}$		X overlaps with Y (English X o verlaps with Y )
${\displaystyle X\mathbf {\operatorname {s} } Y}$ ${\displaystyle Y\mathbf {\operatorname {si} } X}$		X begins with Y at (English X s tarts with Y )
${\displaystyle X\mathbf {\operatorname {d} } Y}$ ${\displaystyle Y\mathbf {\operatorname {di} } X}$		X takes place (English while Y X happens d uring Y )
${\displaystyle X\mathbf {\operatorname {f} } Y}$ ${\displaystyle Y\mathbf {\operatorname {fi} } X}$		X ends with Y (English X f inishes with Y )
${\displaystyle X\mathbf {\operatorname {=} } Y}$		X is equal to Y

With this, given facts can now be formalized and then automatically processed further.

The given sentence

Peter reads the newspaper during dinner. Then he goes to bed.

leads to the following formalization according to Allen calculus:

${\displaystyle {\mbox{Zeitung }}\mathbf {\{\operatorname {d} ,\operatorname {s} ,\operatorname {f} \}} {\mbox{ Abendessen}}}$

${\displaystyle {\mbox{Abendessen }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ Bett}}}$

Linking intervals

In order to close connections that exist between time intervals, the Allen calculus defines a composition table which, based on given relations between and and between and, makes it possible to infer the relation of and . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle Y}$ ${\displaystyle Z}$ ${\displaystyle X}$ ${\displaystyle Z}$

For the example given, it can be said that it must apply. ${\displaystyle {\mbox{Zeitung }}\mathbf {\{\operatorname {m} ,\operatorname {<} \}} {\mbox{ Bett}}}$

Extensions

The Allen calculus can not only be used to describe time intervals, but it is also suitable for representing spatial conditions. For this purpose, the meaning of the relations is changed and now describes the position of two objects to one another.

Three-dimensional objects can also be described by listing the relationships between each coordinate individually.

The RCC8- calculus offers another possibility for spatial closure .

implementation

• A simple Java library that implements the Allen calculus including the path consistency method
• GQR : C ++ library and programs, etc. a. for Allen's interval algebra

See also

• Temporal logic
• logic

literature

• James F. Allen: Maintaining knowledge about temporal intervals . In: Communications of the ACM . 26/11/1983. ACM Press. Pp. 832-843, ISSN  0001-0782
• Bernhard Nebel, Hans-Jürgen Bürckert: Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra. In: Journal of the ACM. Volume 42, 1995, pp. 43-66.
• Peter van Beek, Dennis W. Manchak: The design and experimental analysis of algorithms for temporal reasoning. In: Journal of Artificial Intelligence Research. Volume 4, 1996, pp. 1-18.