Content deleted Content added
Zeno Gantner (talk | contribs) →Implementation: => implementations |
|||
| (33 intermediate revisions by 21 users not shown) | |||
Line 1:
{{Short description|Calculus for temporal reasoning (relating to time instances) of events}}
{{Use dmy dates|date=
'''Allen's interval algebra''' is a [[calculus (disambiguation)|calculus]] for [[spatial-temporal reasoning|temporal reasoning]] that was introduced by [[James F. Allen (computer scientist)|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
Line 20 ⟶ 21:
|<math>X \,\mathrel{\mathbf{<}}\, Y</math>
<math>Y \,\mathrel{\mathbf{>}}\, X</math>
|[[Image:Allen calculus before.png|X
|X
Y is preceded by X
|-
|<math>X \,\mathrel{\mathbf{m}}\, Y</math>
<math>Y \,\mathrel{\mathbf{mi}}\, X</math>
|[[Image:Allen calculus meet.png|X meets Y]]
|X meets Y
Y is met by X (''i'' stands for '''''i'''nverse'') |-
|<math>X \,\mathrel{\mathbf{o}}\, Y</math>
Line 32 ⟶ 35:
|[[Image:Allen calculus overlap.png|X overlaps with Y]]
|X overlaps with Y
Y is overlapped by X
|-
|<math>X \,\mathrel{\mathbf{s}}\, Y</math>
Line 37 ⟶ 41:
|[[Image:Allen calculus start.png|X starts with Y]]
|X starts Y
Y is started by X
|-
|<math>X \,\mathrel{\mathbf{d}}\, Y</math>
Line 42 ⟶ 47:
|[[Image:Allen calculus during.png|X during Y]]
|X during Y
Y contains X
|-
|<math>X \,\mathrel{\mathbf{f}}\, Y</math>
Line 47 ⟶ 53:
|[[Image:Allen calculus finish.png|X finishes with Y]]
|X finishes Y
Y is finished by X
|-
|<math>X \,\mathrel{\mathbf{=}}\, Y</math>
Line 52 ⟶ 59:
|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.▼
To see that the 13 relations are exhaustive, note that each point of <math>X</math> can be at 5 possible locations relative to <math>Y</math>: before, at the start, within, at the end, after. These give <math>5 + 4 + 3 + 2 + 1 = 15</math> possible relative positions for the start and the end of <math>X</math>. Of these, we cannot have <math>X_0 = X_1 = Y_0</math> since <math>X_0 < X_1</math>, and similarly we cannot have <math>X_0 = X_1 = Y_1</math>, 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... [
: ''During dinner, Peter reads the newspaper. Afterwards, he goes to bed.''▼
is formalized in Allen's Interval Algebra as follows:▼
===Composition of relations between intervals===▼
<math>\mbox{newspaper } \mathbf{\{ \operatorname{d}, \operatorname{s}, \operatorname{f} \}} \mbox{ dinner}</math>▼
For reasoning about the relations between temporal intervals, Allen's
▲
<math>\mbox{dinner } \mathbf{\{ \operatorname{<}, \operatorname{m} \}} \mbox{ bed}</math>▼
The sentences
▲In general, the number of different relations between n intervals is 1, 1, 13, 409, 23917, 2244361... [http://oeis.org/A055203 OEIS A055203]. The special case shown above is for n=2.
▲: ''During dinner, Peter reads the newspaper. Afterwards, he goes to bed.''
▲<math>\mbox{newspaper } \mathbf{\{ \operatorname{d
▲===Composition of relations between intervals===
▲For reasoning about the relations between temporal intervals, Allen's Interval Algebra provides a [[Relation composition|composition]] table. Given the relation between <math>X</math> and <math>Y</math> and the relation between <math>Y</math> and <math>Z</math>, the composition table allows for concluding about the relation between <math>X</math> and <math>Z</math>. Together with a [[converse relation|converse]] operation, this turns Allen's Interval Algebra into a [[relation algebra]].
▲For the example, one can infer <math>\mbox{
==Extensions==
Allen's
The study of [[
http://xml.coverpages.org/DeRoseEML2004.pdf</ref>). Its models have more variations depending on whether endpoints of document structures are permitted to be truly co-located, or merely [tangent].
== Temporal primitives ==
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.<ref>CIDOC CRM Version 7.3: https://cidoc-crm.org/versions-of-the-cidoc-crm, section ''Temporal Relation Primitives based on fuzzy boundaries''</ref>
Temporal primitives split up the Allen relations into individual statements about the start or end of the intervals. For example, ''X overlaps with Y'' (<math>X \mathbf{\operatorname{o}} Y</math>) can be split as follows:
* <math>X \mathbf{\operatorname{o}} Y</math> ⇔ ''starts before the start of'' (<math>X</math>,<math>Y</math>) ∧ ''ends after the start of'' (<math>X</math>,<math>Y</math>) ∧ ''ends before the end of'' (<math>X</math>,<math>Y</math>)
In addition, the ''equal to'' of the Allen relations is replaced by ''before or with'' and ''after or with''. A simple example:
* The reign of King [[Harold Godwinson|Harold II]] ''starts before the start of'' the [[Battle of Hastings]]
* The reign/life of Harold II ''ends after or with the start of'' the Battle of Hastings
* The reign/life of Harold II ''ends before or with the end of'' the Battle of Hastings
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 <math>X \mathbf{\operatorname{m}} Y</math>, <math>X \mathbf{\operatorname{o}} Y</math> or <math>X \mathbf{\operatorname{fi}} Y</math> applies (disjunctions such as <math>\mathbf{\{ \operatorname{m}, \operatorname{o}, \operatorname{fi} \}}</math> 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.
== Implementations ==
* [https://code.google.com/p/allenintervalrelationships/ A simple java library implementing the concept of Allen's temporal relations and the path consistency algorithm]
* [https://github.com/Breinify/brein-time-utilities Java library implementing Allen's Interval Algebra] (incl. data and index structures, e.g., [[
* [https://www.w3.org/TR/
* [https://github.com/m-westphal/gqr GQR] is a [[Semantic reasoner|reasoner]] for Allen's interval algebra (and many others)
* [https://github.com/alreich/qualreas 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.
* [https://github.com/dwolter/SparQ SparQ] is a reasoner for Allen's interval algebra (and many others)
* [https://www.metaphorofitself.net/evexl-introduction EveXL] is a small ___domain-specific language for the detection of events that implements the Interval Algebra's operators via ASCII art patterns.
==See also==
* [[Temporal logic]]
* [[Logic]]
* [[Region
* [[Spatial relation]] (analog)
* [[Commonsense reasoning]]
==References==
{{reflist}}
* {{cite journal | first=James F. | last=Allen | title=Maintaining knowledge about temporal intervals | url=http://cse.unl.edu/~choueiry/Documents/Allen-CACM1983.pdf | journal=Communications of the ACM | date=26 November 1983 | publisher=ACM Press | pages=832–843 | issn=0001-0782 | doi=10.1145/182.358434}}▼
* {{cite journal | first1=Bernhard | last1=Nebel | authorlink1=Bernhard Nebel | first2=Hans-Jürgen | last2=Bürckert | title=Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra | url=https://www.dfki.de/web/forschung/publikationen/renameFileForDownload%3Ffilename%3DRR-93-11.pdf%26file_id%3Duploads_1747 | journal=Journal of the ACM | volume=42 | pages=43–66 | date=1995 | doi=10.1145/200836.200848}}▼
==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 | class=cs.AI }}▼
▲* {{cite journal | first=James F. | last=Allen | title=Maintaining knowledge about temporal intervals | url=http://cse.unl.edu/~choueiry/Documents/Allen-CACM1983.pdf | journal=Communications of the ACM |
▲* {{cite journal | first1=Bernhard | last1=Nebel | authorlink1=Bernhard Nebel | first2=Hans-Jürgen | last2=Bürckert | title=Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra | url=https://
▲* {{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 |
[[Category:Knowledge representation]]
[[Category:Constraint programming]]
| |||