Allen's Interval Algebra

In 1983 James F. Allen published a paper [Allen1983-mkti] in which he proposed thirteen basic relations between time intervals that are distinct, exhaustive, and qualitative. 

These relations and the operations on them form Allen's interval algebra

Thirteen basic relations

Allen's thirteen basic relations are illustrated in Table 1.  This table shows all the possible relations that two definite intervals can have.  Each one is defined graphically by a diagram relating two definite intervals a and b, with time running → from left to right.  For example, the first diagram shows that "a precedes b" means that a ends before b begins, with a gap separating them; the second shows that "a meets b" means that b ends when a begins. 

Table 1.  Allen's thirteen basic relations
precedes meets overlaps finished
by
contains starts equals started
by
during finishes overlap-
ped by
met
by
preceded
by
p m o fi di s e si d f oi mi pi
p m o F D s e S d f O M P

The basic relations are listed in Table 1 sorted by the degree to which a begins before b and then within that by the degree to which a ends before b.  We will commonly list them in this order (pmoFDseSdfOMP), as it makes the relations easier to remember and simplifies comparison of general relations. 

Six pairs of the relations are converses.  For example, the converse of "a precedes b" is "b preceded by a"; whenever the first relation is true, its converse is true also.  Table 2 lists the relations with each one beside its converse.  The thirteenth, "equals", is its own converse.  Each pair of converse relation symbols consists of the lowercase and uppercase of the same letter (e.g. p and P; the uppercase letters represent the relations Allen defined as converses). 

Table 2.  Converses of Allen's basic temporal relations
Relation Converse
precedes (p) (P) preceded by
meets (m) (M) met by
overlaps (o) (O) overlapped by
finished by (F) (f) finishes
contains (D) (d) during
starts (s) (S) started by
equals (e)

8192 general relations

Table 3.  Example "Turn on the light"
a (pmMP) b
"John was
in the room"
p p "I touched the
light switch"
m m
M mi
P pi
b (mo) c
"I touched the
light switch"
m m-bc "The light
was on"
o o-bc

The basic relations describe relations between definite intervals.  Indefinite intervals whose exact relation may be uncertain are described by a set of all the basic relations that may apply.  We call such a set of basic relations a general Allen relation, or just an Allen relation. 

For example, "John was not in the room when I touched the switch to turn on the light" [Allen1983-mkti p.837].  Let

Then we can say a(pmMP)b, that is, a precedes, meets, is met by, or is preceded by b; and b(mo)c, that is, b meets or overlaps c.  Table 3 shows these relations. 

There is a general relation for every combination of the thirteen basic relations:  213 or 8192 of them.  Each of the basic relations is a relation, of course, as are all their combinations.  The full relation (pmoFDseSdfOMP) holds between two intervals about whom nothing is known.  The empty relation () has no meaning in terms of relations between actual intervals, but is the result of some operations on interval relations and is needed for subalgebras of Allen's interval algebra (discussed below). 

Operations on relations

Converse examples
~(p) = (moFDseSdfOMP)
~(pmoFD) = (seSdfOMP)
~() = (pmoFDseSdfOMP)

Complement

The complement ~r of a relation r is the relation consisting of all basic relations not in r

From the definition of complement, we see that the converse operation is its own inverse; for every relation r,

~(~r) = r
Composition examples
(m).(m) = (p)
(pm).(pm) = (p)
(oFD).(oFDseS) = (pmoFD)

Composition

The composition (r.s) of two relations (r) and (s) is the relation that holds between a and c if there is a b such that a(r)b and b(s)c; we then write a(r.s)c

Calculation of composition is not simple like the other operations in this section.  It can be determined by going back to the definitions of the relations, and working from there; or by determining the composition of each basic relation from r with each basic relation from s (using a table, perhaps), and taking the union of the results; or by using the "allen" command. 

Composition is not commutative but is both left and right associative, and distributes over union (as seen in the procedure for calculating composition using a table of composition of basic relations). 

Composition is discussed further below

Converse examples
!(p) = (P)
!(pmoFD) = (dfOMP)
!(mM) = (mM)
!() = ()

Converse

The converse !r of a relation r is the relation consisting of the converses of all basic relations in r

From the definition of converse, we see that the converse operation is its own inverse; for every relation r,

!(!r) = r
Intersection examples
(pmo)^(FDseS) = ()
(pFsSf)^(pmoFD) = (pF)
(pmo)^(pmo) = (pmo)

Intersection

The intersection (r^s) of two relations (r) and (s) is the set-theoretic intersection of the two relations; it is the relation composed of all basic relations that are in both (r) and (s). 

Intersection is commutative and associative.

Union examples
(pmo)+(FDseS) = (pmoFDseS)
(pFsSf)+(pmoFD) = (pmoFDsSf)
(pmo)+(pmo) = (pmo)

Union

The intersection (r+s) of two relations (r) and (s) is the set-theoretic intersection of the two relations; it is the relation composed of all basic relations that are in either (r) and (s). 

Union is commutative and associative.

The composition operation

Table 4a gives the composition of any two basic relations.  Such a table can be used in calculating general compositions by hand, but is also interesting in its own right.  There are striking patterns of partial symmetry in the distribution of the results, here highlighted by giving each result value its own background color.  Out of the 8192 relations in the interval algebra, only 27 appear as compositions of basic relations, and each of those comprises either 1, 3, 5, 9 (concur) or all 13 (full) basic relations. 

Table 4a.  Composition of basic interval relations
. p m o F D s e S d f O M P
p (p) (p) (p) (p) (p) (p) (p) (p) (pmosd) (pmosd) (pmosd) (pmosd) full
m (p) (p) (p) (p) (p) (m) (m) (m) (osd) (osd) (osd) (Fef) (DSOMP)
o (p) (p) (pmo) (pmo) (pmoFD) (o) (o) (oFD) (osd) (osd) concur (DSO) (DSOMP)
F (p) (m) (o) (F) (D) (o) (F) (D) (osd) (Fef) (DSO) (DSO) (DSOMP)
D (pmoFD) (oFD) (oFD) (D) (D) (oFD) (D) (D) concur (DSO) (DSO) (DSO) (DSOMP)
s (p) (p) (pmo) (pmo) (pmoFD) (s) (s) (seS) (d) (d) (dfO) (M) (P)
e (p) (m) (o) (F) (D) (s) (e) (S) (d) (f) (O) (M) (P)
S (pmoFD) (oFD) (oFD) (D) (D) (seS) (S) (S) (dfO) (O) (O) (M) (P)
d (p) (p) (pmosd) (pmosd) full (d) (d) (dfOMP) (d) (d) (dfOMP) (P) (P)
f (p) (m) (osd) (Fef) (DSOMP) (d) (f) (OMP) (d) (f) (OMP) (P) (P)
O (pmoFD) (oFD) concur (DSO) (DSOMP) (dfO) (O) (OMP) (dfO) (O) (OMP) (P) (P)
M (pmoFD) (seS) (dfO) (M) (P) (dfO) (M) (P) (dfO) (M) (P) (P) (P)
P full (dfOMP) (dfOMP) (P) (P) (dfOMP) (P) (P) (dfOMP) (P) (P) (P) (P)

In the tables, full=(pmoFDseSdfOMP) and concur=(oFDseSdfO) in order to conserve space. 

Table 4b.  Frequency distribution of
compositions of basic relations.
22 (p) (P)
9 (d) (D)
7 (oFD) (osd) (DSO) (dfO)
6 (pmoFD) (pmosd) (m) (DSOMP) (dfOMP) (M)
5 (o) (O)
4 (s) (pmo) (OMP)
3 full concur (F) (Fef) (seS) (S) (f)
1 (e)
Table 4c.  Basic relation diagrams for compositions of basic relations.
nRelationDiagrams
22 (p) p
22 (P) pi
9 (d) d
9 (D) di
7 (oFD) o fi di
7 (osd) o s d
7 (dfO) d f oi
7 (DSO) di si oi
6 (pmoFD) p m o fi di
6 (pmosd) p m o s d
6 (dfOMP) d f oi mi pi
6 (DSOMP) di si oi mi pi
6 (m) m
6 (M) mi
5 (o) o
5 (O) oi
4 (pmo) p m o
4 (OMP) oi mi pi
4 (s) s
3 (S) si
3 full p m o fi di s e si d f oi mi pi
3 concur o fi di s e si d f oi
3 (F) fi
3 (f) f
3 (Fef) fi e f
3 (seS) s e si
1 (e) e
Table 5.  Inference of relation
a(pseSdfOMP)c
"John was
in the room"
p p "The light
was on"
s s
e e
S si
d d
f f
O oi
M mi
P pi

Composition and inference

The composition operation is the basis for inference among interval relations. 

Let a0(r1)a1, a1(r2)a2, ... , a(n-1)(rn)an be a chain of relations among intervals a0 through an.  Then this chain of relations may be used to infer that

a0(r1.r2. ... .rn)an

For a collection of relations on intervals, we can derive the strongest implied relation between a0 and an by examining all possible chains of inference between a0 and an, and taking the intersection of all the resulting compositions of chained relations.  Each chain of inference places a constraint on the relation, so the inferences are combined by taking their intersection. 

The number of possible chains rises very quickly as the number of relations in the collection is increased. 

A related problem is determining, for a particular collection of relations on indefinite intervals, whether there is any set of specific time values for the intervals such that all the relations in the collection are true.  This is the satisfaction problem for Allen's interval algebra, and it has been shown to be NP-complete [Vilain+Kautz+Beek1989-cpat]. 

Unsatisfiable graph

Figure 1.  Unsatisfiable relations

A simple example of a collection of relations and intervals that is not satisfiable is three intervals a, b, and c such that a(p)b, b(p)c, and c(p)a (each precedes the next, and the last precedes the first).  There are no definite intervals for which all these relations can hold.  We can calculate that this collection is unsatisfiable by inferring the relation that is implied between a and c by the other relations.  The inferred relation through b is

(a to b).(b to c) = (p).(p) = (p)

We already know that the relation between as the relation between c and a is (P) (the converse of the relation (p) between a and c).  The strongest inferred relation between c and a is the intersection of these two relations

(p)∩ (P) = ∅

∅ means that c and a have no relation at all, which is not possible; so this collection of intervals and relations is unsatisfiable. 

Relationships between Allen relations

The relationships between Allen relations are defined in terms of the corresponding sets of basic relations. 

Two Allen relations are equal if they contain the same basic relations, and not equal otherwise. 

Weaker/stronger examples
(pmoFD)<(oDF) (pmoFD) is weaker than (oDF)
(pmo)>(pmoFD) (pmo) is stronger than (pmoFD)
(oDF)#(pmo) (oDF) and (pmo) are incomparable

The Allen relations form a partial order; we say that one relation can be weaker than another, (or conversely, stronger).  This partial order is the same as the partial order on the sets of basic Allen relations defined by ⊃.  Relation A is weaker than relation B if AB.  If the sets A and B are not comparable by ⊃, then the general relations A and B are incomparable also. 

Because we naturally think of "stronger" as bigger than "weaker", we write A<B to indicate A is weaker.  Note that A<B is equivalent to AB; the < and ⊃ point in opposite directions. 

Eighteen maximal tractable subalgebras

A examples
innot in
()(pmo)
(e)(s)
(seS)(sS)

Although satisfaction in interval algebra is NP-complete, there are subsets of the 8192 relations for which satisfaction is tractable (a polynomial-time algorithm exists).  Once such subsets have been found, a natural course of action is to maximize their size by adding more relations, stopping just before an intractable subset results; the result is a tractable subset that cannot accept another relation without becoming intractable, and is thus maximal.  It turns out that there are eighteen maximal tractable subsets of Allen's interval algebra; every tractable subset of the full algebra is a subset of one or more of these eighteen [Krokhin+Jeavons+Jonsson2003-rtrt].  The maximal tractable subsets are all algebras, that is, each is closed under composition, converse, intersection, and union (a set is closed under an operation if the result of applying the operation to any element(s) of the set is another member of the set).  Thus they are usually described as maximal tractable subalgebras. 

The eighteen maximal tractable subalgebras are listed in Table 6, along with rules defining which relations belong to them and links to the sets of elements in each one.  The most important one is the H or Horn subalgebra; it is the only one of the eighteen that contains all 13 of the basic relations, and inference in it can be done using the path consistency algorithm rather than a more complex one. 

A1 examples
innot in
()(p)
(pS)(ps)
(sOMP)(SOP)

The rules give properties that each member of the subalgebra must have.  For example, for a relation r to be a member of the A subalgebra, if r is not the empty relation, it must contain e.  Thus (), (e), and (Fef) are members, but not (m) or (pmoFD)

The rules appear in pairs, labelled + and −.  The relations named in each pair are converses.  The rules that appear as singletons are those whose relations are their own converses (like () and (e) in the A rule).  For example, for a relation r to be a member of A1, if r has any basic relations in common with (pmoFD), then r must contain S.  The converses of (pmoFD) and (S) are (dfOMP) and (s), respectively, and the − rule says that if r has any basic relations in common with (dfOMP), then r must contain s.  In the literature, this pair of rules is often expressed as

A1 = {r | r∩ (pmoFD)±1 ≠ ∅ ⇒ (p)±1r}

where the superscript ±1 indicates the relation and its converse respectively in the two rules of the pair. 

Table 6.  Tractable subalgebras (from Krokhin et al.)
Name RulesSize
A r() (e) ⊆ r 4097 elements
A1 +) r ∩ (pmoFD) () (S) ⊆ r 2178 elements
−) r ∩ (dfOMP) () (s) ⊆ r
A2 +) r ∩ (pmoFD) () (s) ⊆ r 2178 elements
−) r ∩ (dfOMP) () (S) ⊆ r
A3 +) r ∩ (pmodf) () (s) ⊆ r 2178 elements
−) r ∩ (FDOMP) () (S) ⊆ r
A4 +) r ∩ (pmoFd) () (s) ⊆ r 2178 elements
−) r ∩ (DfOMP) () (S) ⊆ r
B1 +) r ∩ (pmosd) () (F) ⊆ r 2178 elements
−) r ∩ (DSOMP) () (f) ⊆ r
B2 +) r ∩ (pmosd) () (f) ⊆ r 2178 elements
−) r ∩ (DSOMP) () (F) ⊆ r
B3 +) r ∩ (pmoDS) () (F) ⊆ r 2178 elements
−) r ∩ (sdOMP) () (f) ⊆ r
B4 +) r ∩ (pmoDs) () (F) ⊆ r 2178 elements
−) r ∩ (SdOMP) () (f) ⊆ r
Ed +) r ∩ (pmosd) () (d) ⊆ r 2312 elements
−) r ∩ (DSOMP) () (D) ⊆ r
Eo +) r ∩ (pmosd) () (o) ⊆ r 2312 elements
−) r ∩ (DSOMP) () (O) ⊆ r
Ep +) r ∩ (pmosd) () (p) ⊆ r 2312 elements
−) r ∩ (DSOMP) () (P) ⊆ r
E* 1+) r ∩ (pmosd) () (s) ⊆ r 1445 elements
1−) r ∩ (DSOMP) () (S) ⊆ r
2) r ∩ (Ff) () (e) ⊆ r
H 1+) r ∩ (os) () & r ∩ (Of) ≠ () (d) ⊆ r 868 elements
1−) r ∩ (SO) () & r ∩ (oF) ≠ () (D) ⊆ r
2+) r ∩ (sd) () & r ∩ (FD) ≠ () (o) ⊆ r
2−) r ∩ (DS) () & r ∩ (df) ≠ () (O) ⊆ r
3+) r ∩ (pm) () & ¬(r ⊆ (pm)) (o) ⊆ r
3−) r ∩ (MP) () & ¬(r ⊆ (MP)) (O) ⊆ r
Sd +) r ∩ (pmoFD) () (D) ⊆ r 2312 elements
−) r ∩ (dfOMP) () (d) ⊆ r
So +) r ∩ (pmoFD) () (o) ⊆ r 2312 elements
−) r ∩ (dfOMP) () (O) ⊆ r
Sp +) r ∩ (pmoFD) () (p) ⊆ r 2312 elements
−) r ∩ (dfOMP) () (P) ⊆ r
S* 1+) r ∩ (pmoFD) () (F) ⊆ r 1445 elements
1−) r ∩ (dfOMP) () (f) ⊆ r
2+) r ∩ (pmoFD) () (F) ⊆ r
2−) r ∩ (dfOMP) () (f) ⊆ r

Networks of relations

Example as graph

Figure 2.  Example as graph

The Allen relations among three or more intervals form a graph whose nodes are the intervals and whose edges are the relations.  The light switch example from Table 3 can be presented as a graph as in Figure 2.  This graph is not complete — there is no edge from node a to node c. Instead, only the known relations are presented. 

Example as graph

Figure 3.  Complete graph

The graph may be completed by inferring the relations corresponding to each missing edge (Figure 3).  In this case, the missing edge is (pmMP).(mo) = (pseSdfOMP).  Inference of missing edges is equivalent to solving for satisfaction, which in the general case is NP-complete.  For the H subclass, the path-consistency algorithm may be used for complete inference and determining satisfiability [Gennari1998-trcp p.194ff]. 

Equivalence of two networks

Two complete networks are equivalent if they contain the same intervals, and the relations between corresponding intervals are the same. 

If one or both the networks are not complete, then they are equivalent if the corresponding completed networks are equivalent. 

Specialization of a network

A complete network α is a specialization of another complete network β if

  1. Nodes(α) ⊇ Nodes(β)
    (every interval in β is present in α)
  2. For all corresponding edges a of α and b of β, ab
    (every relation in α is the same or stronger than the corresponding relation in β)

If one or both the networks are not complete, then α specializes β if the completion of α specialized the completion of β. 

Informally, a network can be specialized into another network that meets all the first one's constraints.  This can't happen if the specialization doesn't have all the intervals, nor if the specialization has a weaker edge.  A mnemonic is "specialization means bigger and stronger". 

Partial order of the basic relations

Figure 4.  Partial order of the basic relations

Ordering the basic relations

The standard order I selected isn't the only plausible one.  Figure 4 shows a partial order of the basic relations, in which each relation is obtained from the one(s) immediately above it by nudging one end of a to or beyond the next end of b

Other names and symbols for the basic relations

Table 7.  Names and symbols for the basic relations
Here Allen Krokhin et al.
p precedes p before < precedes p
m meets m meets m meets m
o overlaps o overlaps o overlaps o
fi finished-by F finished-by fi finished-by f-1
di contains d contains di contains d-1
s starts s starts s starts s
e equals e equals = equals
si started-by s started-by si started-by s-1
d during d during d during d
f finishes f finishes f finishes f
oi overlapped-by O overlapped-by oi overlapped-by o-1
mi met-by M met-by mi met-by m-1
pi preceded-by P after > preceded-by p-1

References

Allen, James F.  "Maintaining knowledge about temporal intervals".  Communications of the ACM 26(11) pp.832-843, Nov. 1983. 

Gennari, Rosella.  Temporal Reasoning and Constraint Programming: A survey.  CWI Quarterly, 11(2-3):163-214.  1998.

Andrei Krokhin, Peter Jeavons, and Peter Jonsson.  "Reasoning about temporal relations:  The tractable subalgebras of Allen's interval algebra".  Journal of the ACM 50(5), pp. 591-640, 2003. 

Marc Vilain, Henry Kautz, and Peter van Beek.  "Constraint propagation algorithms for temporal reasoning: a revised report".  In Readings in qualitative reasoning about physical systems, edited by D. S. Weld and J. de Kleer, pp. 373-381, 1989.

Valid XHTML 1.0 Strict
Valid CSS!
2009Sep23We10:12
Thomas A. Alspaugh