Allen's Interval Algebra thomasalspaugh.org/pub/fnd/allen.html

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.

distinct because no pair of definite intervals can be related by more than one of the relationships
exhaustive because any pair of definite intervals are described by one of the relations
qualitative (rather than quantitative) because no numeric time spans are considered

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 begins when a ends.

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	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	"I touched the light switch"
	m
	M
	P
b	(mo)	c
"I touched the light switch"	m	"The light was on"
"I touched the light switch"	o	"The light was on"

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

a be the time John was in the room,
b be the time I touched the light switch, and
c be the time the light was on.

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: 2¹³ 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 union (r+s) of two relations (r) and (s) is the set-theoretic union of the two relations; it is the relation composed of all basic relations that are in either (r) or (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	(pmo)	(OMP)
3	full	concur	(F)	(Fef)	(seS)	(s)	(S)	(f)
1	(e)

Table 4c. Basic relation diagrams for compositions of basic relations.
n	Relation	Diagrams
22	(p)
22	(P)
9	(d)
9	(D)
7	(oFD)
7	(osd)
7	(dfO)
7	(DSO)
6	(pmoFD)
6	(pmosd)
6	(dfOMP)
6	(DSOMP)
6	(m)
6	(M)
5	(o)
5	(O)
4	(pmo)
4	(OMP)
4	(s)
3	(S)
3	full
3	concur
3	(F)
3	(f)
3	(Fef)
3	(seS)
1	(e)

Table 5. Inference of relation
a	(pseSdfOMP)	c
"John was in the room"	p	"The light was on"
	s
	e
	S
	d
	f
	O
	M
	P

Composition and inference

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

Let a₀(r₁)a₁, a₁(r₂)a₂, ... , a_(n-1)(r_n)a_n be a chain of relations among intervals a₀ through a_n. Then this chain of relations may be used to infer that

a₀(r₁.r₂. ... .r_n)a_n

For a collection of relations on intervals, we can derive the strongest implied relation between a₀ and a_n by examining all possible chains of inference between a₀ and a_n, 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].

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 A⊃B. 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 A⊃B; the < and ⊃ point in opposite directions.

Eighteen maximal tractable subalgebras

A_≡ examples
in	not 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, and intersection (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.

A₁ examples
in	not 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 A₁, 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

A₁ = {r | r∩ (pmoFD)^±1 ≠ ∅ ⇒ (p)^±1 ⊆ r}

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	Rules							Size
A_≡		r ≠ ()		⇒	(e) ⊆ r			4097 elements
A₁	+)	r ∩ (pmoFD)	≠ ()	⇒	(S) ⊆ r			2178 elements
A₁	−)	r ∩ (dfOMP)	≠ ()	⇒	(s) ⊆ r			2178 elements
A₂	+)	r ∩ (pmoFD)	≠ ()	⇒	(s) ⊆ r			2178 elements
A₂	−)	r ∩ (dfOMP)	≠ ()	⇒	(S) ⊆ r			2178 elements
A₃	+)	r ∩ (pmodf)	≠ ()	⇒	(s) ⊆ r			2178 elements
A₃	−)	r ∩ (FDOMP)	≠ ()	⇒	(S) ⊆ r			2178 elements
A₄	+)	r ∩ (pmoFd)	≠ ()	⇒	(s) ⊆ r			2178 elements
A₄	−)	r ∩ (DfOMP)	≠ ()	⇒	(S) ⊆ r			2178 elements
B₁	+)	r ∩ (pmosd)	≠ ()	⇒	(F) ⊆ r			2178 elements
B₁	−)	r ∩ (DSOMP)	≠ ()	⇒	(f) ⊆ r			2178 elements
B₂	+)	r ∩ (pmosd)	≠ ()	⇒	(f) ⊆ r			2178 elements
B₂	−)	r ∩ (DSOMP)	≠ ()	⇒	(F) ⊆ r			2178 elements
B₃	+)	r ∩ (pmoDS)	≠ ()	⇒	(F) ⊆ r			2178 elements
B₃	−)	r ∩ (sdOMP)	≠ ()	⇒	(f) ⊆ r			2178 elements
B₄	+)	r ∩ (pmoDs)	≠ ()	⇒	(F) ⊆ r			2178 elements
B₄	−)	r ∩ (SdOMP)	≠ ()	⇒	(f) ⊆ r			2178 elements
E_d	+)	r ∩ (pmosd)	≠ ()	⇒	(d) ⊆ r			2312 elements
E_d	−)	r ∩ (DSOMP)	≠ ()	⇒	(D) ⊆ r			2312 elements
E_o	+)	r ∩ (pmosd)	≠ ()	⇒	(o) ⊆ r			2312 elements
E_o	−)	r ∩ (DSOMP)	≠ ()	⇒	(O) ⊆ r			2312 elements
E_p	+)	r ∩ (pmosd)	≠ ()	⇒	(p) ⊆ r			2312 elements
E_p	−)	r ∩ (DSOMP)	≠ ()	⇒	(P) ⊆ r			2312 elements
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
S_d	+)	r ∩ (pmoFD)	≠ ()	⇒	(D) ⊆ r			2312 elements
S_d	−)	r ∩ (dfOMP)	≠ ()	⇒	(d) ⊆ r			2312 elements
S_o	+)	r ∩ (pmoFD)	≠ ()	⇒	(o) ⊆ r			2312 elements
S_o	−)	r ∩ (dfOMP)	≠ ()	⇒	(O) ⊆ r			2312 elements
S_p	+)	r ∩ (pmoFD)	≠ ()	⇒	(p) ⊆ r			2312 elements
S_p	−)	r ∩ (dfOMP)	≠ ()	⇒	(P) ⊆ r			2312 elements
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

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.

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

Nodes(α) ⊇ Nodes(β)
(every interval in β is present in α)
For all corresponding edges a of α and b of β, a≥b
(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".

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.
precedes	p	before	<	precedes	p
meets	m	meets	m	meets	m
overlaps	o	overlaps	o	overlaps	o
finished-by	F	finished-by	fi	finished-by	f^-1
contains	d	contains	di	contains	d^-1
starts	s	starts	s	starts	s
equals	e	equals	=	equals	≡
started-by	S	started-by	si	started-by	s^-1
during	d	during	d	during	d
finishes	f	finishes	f	finishes	f
overlapped-by	O	overlapped-by	oi	overlapped-by	o^-1
met-by	M	met-by	mi	met-by	m^-1
preceded-by	P	after	>	preceded-by	p^-1

Acknowledgments

I thank Philippus Baalman, Tassilo Karge, Richard Allen (no relation), and Thomas S. Dye for pointing out errors in earlier versions of this page.

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.