Algèbre des intervalles d'Allen

En logique, l'algèbre des intervalles d'Allen est un calcul pour les raisonnements spatio-temporels créé par James F. Allen en 1983. Cette algèbre définit les relations possibles entre des intervalles de temps et propose une table de composition. Elle peut être utilisée comme base pour des raisonnements portant sur la description temporelle d'événements.

Description formelle

Relations

L'algèbre des intervalles d'Allen définit 13 relations, qui représentent toutes les relations possibles entre deux intervalles.

Relation	Illustration	Interprétation
$X\mathbf {\operatorname {<} } Y$ $Y\mathbf {\operatorname {>} } X$		X se déroule avant Y (before et after)
$X\mathbf {\operatorname {m} } Y$ $Y\mathbf {\operatorname {mi} } X$		X rencontre Y (meets) (i signifie inverse)
$X\mathbf {\operatorname {o} } Y$ $Y\mathbf {\operatorname {oi} } X$		X chevauche Y (overlaps)
$X\mathbf {\operatorname {s} } Y$ $Y\mathbf {\operatorname {si} } X$		X démarre Y (starts)
$X\mathbf {\operatorname {d} } Y$ $Y\mathbf {\operatorname {di} } X$		X se déroule pendant Y (during)
$X\mathbf {\operatorname {f} } Y$ $Y\mathbf {\operatorname {fi} } X$		X termine Y (finishes)
$X\mathbf {\operatorname {=} } Y$		X est égal à Y

Avec cette algèbre, des évènements peuvent être formalisés et utilisés pour effectuer des raisonnements automatisés. Les relations entre les intervalles sont formalisées par un sous-ensemble de ces 13 relations.

Ainsi la phrase « Pendant le diner, Pierre lit le journal. Ensuite, il va se coucher. » sera formalisée ainsi par l'algèbre des intervalles d'Allen :

${\mbox{journal }}\mathbf {\{\operatorname {d} ,\operatorname {s} ,\operatorname {f} \}} {\mbox{ dîner}}$

${\mbox{dîner }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ sommeil}}$

Généralement, le nombre de relations possibles entre n intervalles est 1, 1, 13, 409, 23917, 2244361... OEIS A055203. Le cas précédent s'applique avec n=2.

Composition de relations entre des intervalles

Pour raisonner sur les relations entre des intervalles temporels, l'algèbre des intervalles d'Allen propose une table de composition. Étant données les relations entre $X$ et $Y$, ainsi que les relations entre $Y$ et $Z$, la table de composition permet de déduire les relations possibles entre $X$ et $Z$. Avec la composition de relations, ainsi qu'une opération d'inversion, l'algèbre des intervalles d'Allen est définie comme une algèbre relationnelle.

Par exemple, il est possible d'inférer ${\mbox{journal }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ sommeil}}$.

Extensions

L'algèbre des intervalles d'Allen peut être utilisée à la fois pour décrire des intervalles temporels et des configurations spatiales. Dans le second cas, les relations sont considérées comme décrivant la position relative d'objets dans l'espace. Cela est aussi possible pour des objets en 3 dimensions en listant séparément les relations pour chaque coordonnée.

Implémentation

• (en) Une bibliothèque Java qui implémente l'algèbre des intervalles d'Allen ainsi qu'un algorithme de propagation de contrainte pour l'opération de composition
• Une bibliothèque Java qui implémente l'algèbre des intervalles d'Allen (y compris pour les données et les structures d'index, par exemple arbre d'intervalles)
• GQR est un outil pour raisonner sur l'algèbre des intervalles d'Allen (et d'autres)
• qualreas est un cadriciel Python pour le raisonnement qualitatif sur les réseaux d'algèbres relationnelles, telles que RCC-8 ou l'algèbre des intervalles d'Allen.
• SparQ est un outil pour raisonner sur l'algèbre des intervalles d'Allen (et d'autres)

Références

• (en) James F. Allen, « Maintaining knowledge about temporal intervals », Communications of the ACM, ACM Press,‎ 26 novembre 1983, p. 832–843 (ISSN 0001-0782, DOI 10.1016/B978-1-4832-1447-4.50033-X)
• (en) Bernhard Nebel et Hans-Jürgen Bürckert, « Reasoning about Temporal Relations: A Maximal Tractable Subclass of Allen's Interval Algebra », Journal of the ACM,‎ 1995, p. 43–66
• (en) Peter van Beek et Dennis W. Manchak, « The design and experimental analysis of algorithms for temporal reasoning », Journal of Artificial Intelligence Research,‎ 1996, p. 1–18

Articles connexes

• Logique temporelle
• Logique