Allen-Kalkül
# Allen-Kalkül

Der Allen-Kalkül, auch Allens Intervallalgebra genannt, ist eine Logik zur Repräsentation von zeitlichen Zusammenhängen und zum logischen Schließen, welche 1983 von James F. Allen vorgestellt wurde.

Der Kalkül 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 | 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.

## 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
