Algèbre des intervalles d'Allen

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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[modifier | modifier le code]

Relations[modifier | modifier le code]

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 se déroule avant Y X se déroule avant Y

X rencontre Y X rencontre Y (meets) (i signifie inverse)

X chevauche Y (meets) X chevauche Y (overlaps)

X démarre Y X démarre Y (starts)

X se déroule pendant Y X se déroule pendant Y (during)

X termine Y X termine Y (finishes)
X est égal à 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 :

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[modifier | modifier le code]

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 et , ainsi que les relations entre et , la table de composition permet de déduire les relations possibles entre et . 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 .

Extensions[modifier | modifier le code]

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[modifier | modifier le code]

Références[modifier | modifier le code]

  • (en) James F. Allen, « Maintaining knowledge about temporal intervals », Communications of the ACM, ACM Press,‎ , p. 832–843 (ISSN 0001-0782)
  • (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,‎ , 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,‎ , p. 1–18

Articles connexes[modifier | modifier le code]

Sur les autres projets Wikimedia :