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 se déroule avant Y (before et after)

X rencontre Y (meets) (i signifie inverse)

X chevauche Y (overlaps)

X démarre Y (starts)

X se déroule pendant Y (during)

X termine Y (finishes)
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

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

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

Références

  • (en) James F. Allen, « Maintaining knowledge about temporal intervals », Communications of the ACM, ACM Press, , 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, , 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

  • Portail des mathématiques
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.