Algèbre des intervalles d'Allen

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
${\displaystyle X\mathbf {\operatorname {<} } Y}$ ${\displaystyle Y\mathbf {\operatorname {>} } X}$		X se déroule avant Y (before et after)
${\displaystyle X\mathbf {\operatorname {m} } Y}$ ${\displaystyle Y\mathbf {\operatorname {mi} } X}$		X rencontre Y (meets) (i signifie inverse)
${\displaystyle X\mathbf {\operatorname {o} } Y}$ ${\displaystyle Y\mathbf {\operatorname {oi} } X}$		X chevauche Y (overlaps)
${\displaystyle X\mathbf {\operatorname {s} } Y}$ ${\displaystyle Y\mathbf {\operatorname {si} } X}$		X démarre Y (starts)
${\displaystyle X\mathbf {\operatorname {d} } Y}$ ${\displaystyle Y\mathbf {\operatorname {di} } X}$		X se déroule pendant Y (during)
${\displaystyle X\mathbf {\operatorname {f} } Y}$ ${\displaystyle Y\mathbf {\operatorname {fi} } X}$		X termine Y (finishes)
${\displaystyle 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 :

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

${\displaystyle {\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.

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 ${\displaystyle X}$ et ${\displaystyle Y}$, ainsi que les relations entre ${\displaystyle Y}$ et ${\displaystyle Z}$, la table de composition permet de déduire les relations possibles entre ${\displaystyle X}$ et ${\displaystyle 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 ${\displaystyle {\mbox{journal }}\mathbf {\{\operatorname {<} ,\operatorname {m} \}} {\mbox{ sommeil}}}$.