Allen-Kalkül

Der Allen-Kalkül, auch Allens Intervallalgebra genannt, ist ein Kalkül für die Temporale Logik, welches 1983 von James F. Allen vorgestellt wurde. Es definiert mögliche zeitliche Zusammenhänge zwischen Intervallen und beschreibt einen Algorithmus, um basierend auf zeitlichen Beschreibungen von Ereignissen Schlüsse zwischen diesen ziehen zu können.

Formale Beschreibung

Relationen

Mit Hilfe der abgebildeten 13 Relationen ist es möglich alle möglichen Zusammenhänge zwischen genau zwei Intervallen zu beschreiben. Die Relationen beinhalten auch die Inversen.

Relation	Illustration	Interpretation
$X\mathbf {\operatorname {<} } Y$ $Y\mathbf {\operatorname {>} } X$		X findet vor Y statt
$X\mathbf {\operatorname {m} } Y$ $Y\mathbf {\operatorname {mi} } X$		X trifft auf Y (englisch X meets Y, das i steht für inverse)
$X\mathbf {\operatorname {o} } Y$ $Y\mathbf {\operatorname {oi} } X$		X überschneidet sich mit Y (englisch X overlaps with Y)
$X\mathbf {\operatorname {s} } Y$ $Y\mathbf {\operatorname {si} } X$		X fängt mit Y an (englisch X starts with Y)
$X\mathbf {\operatorname {d} } Y$ $Y\mathbf {\operatorname {di} } X$		X findet während Y statt (englisch X happens during Y)
$X\mathbf {\operatorname {f} } Y$ $Y\mathbf {\operatorname {fi} } X$		X hört mit Y auf (englisch X finishes with Y)
$X\mathbf {\operatorname {=} } Y$		X ist gleich Y

Hiermit können nun gegebene Fakten formalisiert und anschließend automatisch weiterverarbeitet werden.

Der gegebene Satz

Peter liest während des Abendessens die Zeitung. Anschließend geht er zu Bett.

führt zu folgender Formalisierung gemäß Allen-Kalkül:

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

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

Verknüpfungen von Intervallen

Zum Schließen von Zusammenhängen, welche zwischen Zeitintervallen bestehen, definiert der Allen-Kalkül eine Kompositionstabelle, welche es ermöglicht anhand von gegebenen Relationen zwischen $X$ und $Y$ und zwischen $Y$ und $Z$ auf die Relation von $X$ und $Z$ zu schließen.

So kann für das gegebene Beispiel gesagt werden, dass ${\mbox{Zeitung }}\mathbf {\{\operatorname {m} ,\operatorname {<} \}} {\mbox{ Bett}}$ gelten muss.

Erweiterungen

Der Allen-Kalkül kann nicht nur zur Beschreibung von zeitlichen Intervallen verwendet werden, sondern er eignet sich auch zur Darstellung von räumlichen Gegebenheiten. Hierzu wird die Bedeutung der Relationen verändert und beschreibt nun die Lage zweier Objekte zueinander.

Dabei können auch dreidimensionale Objekte beschrieben werden, in dem die Zusammenhänge jeder Koordinate einzeln aufgelistet werden.

Eine weitere Möglichkeit zum räumlichen Schließen bietet der RCC8-Kalkül.

Temporal primitives

In der Kulturerbe-Ontologie CIDOC CRM werden die Allen-Relationen durch sogenannte Temporal Primitives ersetzt, die das Formulieren belegbarer Aussagen im Bereich des Cultural Heritage sowie das Reasoning über diese Aussagen erleichtern. Temporal Primitives teilen die Allen-Relationen in einzelne Aussagen über den Anfang oder das Ende der Intervalle auf. Zum Beispiel X überschneidet sich mit Y ($X\mathbf {\operatorname {o} } Y$) kann folgendermaßen aufgeteilt werden:

• $X\mathbf {\operatorname {o} } Y$ ⇔ starts before the start of ($X$,$Y$) ∧ ends after the start of ($X$,$Y$) ∧ ends before the end of ($X$,$Y$)

Außerdem wird das gleich der Allen-Relationen ersetzt durch vor oder gleich sowie nach oder gleich. Ein einfaches Beispiel:

• The reign of King 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 dem Beispiel muss nicht festgelegt werden, ob Harald II. am Anfang oder während oder am Ende der Schlacht getötet wurde, also ob $X\mathbf {\operatorname {m} } Y$, $X\mathbf {\operatorname {o} } Y$ oder $X\mathbf {\operatorname {fi} } Y$ zutrifft (Disjunktionen wie $\mathbf {\{\operatorname {m} ,\operatorname {o} ,\operatorname {fi} \}}$ können in CIDOC CRM nicht ausgedrückt werden und sind nur in Suchanfragen möglich). Wenn es für eine konkrete historische Fragestellung relevant ist, kann es später noch spezifiziert werden, z. B. mit ends after the start of.

CIDOC CRM unterscheidet zwischen Ereignissen und ihren zugehörigen Intervallen. Allen relations und temporal primitives sind Aussagen über Ereignisse und nur im Ergebnis auch Aussagen über ihre Intervalle. Ein weiterer Unterschied ist, dass zeitliche, räumliche und raumzeitliche Entitäten in CIDOC CRM fuzzy Ränder haben. Insbesondere die exakte Gleichzeitigkeit zweier Ereignisse ist sonst extrem selten.

Implementierung

• Eine einfache Java-Bibliothek, welche das Allen-Kalkül inklusive der Pfadkonsistenz-Methode implementiert
• GQR: C++-Bibliothek und Programme, u. a. für Allens Intervallalgebra

Literatur

• James F. Allen: Maintaining knowledge about temporal intervals. In: Communications of the ACM. 26/11/1983. ACM Press. S. 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. Band 42, 1995, S. 43–66.
• Peter van Beek, Dennis W. Manchak: The design and experimental analysis of algorithms for temporal reasoning. In: Journal of Artificial Intelligence Research. Band 4, 1996, S. 1–18.