Sets
Relations
Correspondences
Ordered Sets
Lattices
Graphs
Powersets
Binary Strings
Logic
AIA
Greek
Glossary
Abstracts
Argument
Glossaries
Inquiry Cycle
Legal Relations
Presentations
Elicitation
Glossaries
Goals
i*
SCR
Tracing
Design Patterns
Javadoc
Java Packages
Java Types
In 1983 James F. Allen published a paper [Allen1983mkti] 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.
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.
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).
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) 
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" 

o 
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" [Allen1983mkti 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: 2^{13} 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).
Converse examples 

~(p) = (moFDseSdfOMP) 
~(pmoFD) = (seSdfOMP) 
~() = (pmoFDseSdfOMP) 
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,
Composition examples 

(m).(m) = (p) 
(pm).(pm) = (p) 
(oFD).(oFDseS) = (pmoFD) 
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) 
!() = () 
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,
Intersection examples 

(pmo)^(FDseS) = () 
(pFsSf)^(pmoFD) = (pF) 
(pmo)^(pmo) = (pmo) 
The intersection (r^s) of two relations (r) and (s) is the settheoretic 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) 
The intersection (r+s) of two relations (r) and (s) is the settheoretic 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.
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.
.  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.
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) 
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) 
a  (pseSdfOMP)  c  
"John was in the room" 
p  "The light was on" 

s  
e  
S  
d  
f  
O  
M  
P 
The composition operation is the basis for inference among interval relations.
Let a_{0}(r_{1})a_{1}, a_{1}(r_{2})a_{2}, ... , a_{(n1)}(r_{n})a_{n} be a chain of relations among intervals a_{0} through a_{n}. Then this chain of relations may be used to infer that
For a collection of relations on intervals, we can derive the strongest implied relation between a_{0} and a_{n} by examining all possible chains of inference between a_{0} 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 NPcomplete [Vilain+Kautz+Beek1989cpat].
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
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
∅ means that c and a have no relation at all, which is not possible; so this collection of intervals and relations is unsatisfiable.
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.
A_{≡} examples  

in  not in 
()  (pmo) 
(e)  (s) 
(seS)  (sS) 
Although satisfaction in interval algebra is NPcomplete, there are subsets of the 8192 relations for which satisfaction is tractable (a polynomialtime 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+Jonsson2003rtrt]. 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.
A_{1} 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_{1}, 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
where the superscript ±1 indicates the relation and its converse respectively in the two rules of the pair.
Name  Rules  Size  

A_{≡}  r ≠ ()  ⇒  (e) ⊆ r  4097 elements  
A_{1}  +)  r ∩ (pmoFD)  ≠ ()  ⇒  (S) ⊆ r  2178 elements  
−)  r ∩ (dfOMP)  ≠ ()  ⇒  (s) ⊆ r  
A_{2}  +)  r ∩ (pmoFD)  ≠ ()  ⇒  (s) ⊆ r  2178 elements  
−)  r ∩ (dfOMP)  ≠ ()  ⇒  (S) ⊆ r  
A_{3}  +)  r ∩ (pmodf)  ≠ ()  ⇒  (s) ⊆ r  2178 elements  
−)  r ∩ (FDOMP)  ≠ ()  ⇒  (S) ⊆ r  
A_{4}  +)  r ∩ (pmoFd)  ≠ ()  ⇒  (s) ⊆ r  2178 elements  
−)  r ∩ (DfOMP)  ≠ ()  ⇒  (S) ⊆ r  
B_{1}  +)  r ∩ (pmosd)  ≠ ()  ⇒  (F) ⊆ r  2178 elements  
−)  r ∩ (DSOMP)  ≠ ()  ⇒  (f) ⊆ r  
B_{2}  +)  r ∩ (pmosd)  ≠ ()  ⇒  (f) ⊆ r  2178 elements  
−)  r ∩ (DSOMP)  ≠ ()  ⇒  (F) ⊆ r  
B_{3}  +)  r ∩ (pmoDS)  ≠ ()  ⇒  (F) ⊆ r  2178 elements  
−)  r ∩ (sdOMP)  ≠ ()  ⇒  (f) ⊆ r  
B_{4}  +)  r ∩ (pmoDs)  ≠ ()  ⇒  (F) ⊆ r  2178 elements  
−)  r ∩ (SdOMP)  ≠ ()  ⇒  (f) ⊆ r  
E_{d}  +)  r ∩ (pmosd)  ≠ ()  ⇒  (d) ⊆ r  2312 elements  
−)  r ∩ (DSOMP)  ≠ ()  ⇒  (D) ⊆ r  
E_{o}  +)  r ∩ (pmosd)  ≠ ()  ⇒  (o) ⊆ r  2312 elements  
−)  r ∩ (DSOMP)  ≠ ()  ⇒  (O) ⊆ r  
E_{p}  +)  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  
S_{d}  +)  r ∩ (pmoFD)  ≠ ()  ⇒  (D) ⊆ r  2312 elements  
−)  r ∩ (dfOMP)  ≠ ()  ⇒  (d) ⊆ r  
S_{o}  +)  r ∩ (pmoFD)  ≠ ()  ⇒  (o) ⊆ r  2312 elements  
−)  r ∩ (dfOMP)  ≠ ()  ⇒  (O) ⊆ r  
S_{p}  +)  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 
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 NPcomplete. For the H subclass, the pathconsistency algorithm may be used for complete inference and determining satisfiability [Gennari1998trcp p.194ff].
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.
A complete network α is a specialization of another complete network β if
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
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.
Here  Allen  Krokhin et al.  

precedes  p  before  <  precedes  p  
meets  m  meets  m  meets  m  
overlaps  o  overlaps  o  overlaps  o  
finishedby  F  finishedby  fi  finishedby  f^{1}  
contains  d  contains  di  contains  d^{1}  
starts  s  starts  s  starts  s  
equals  e  equals  =  equals  ≡  
startedby  s  startedby  si  startedby  s^{1}  
during  d  during  d  during  d  
finishes  f  finishes  f  finishes  f  
overlappedby  O  overlappedby  oi  overlappedby  o^{1}  
metby  M  metby  mi  metby  m^{1}  
precededby  P  after  >  precededby  p^{1} 
Allen, James F. "Maintaining knowledge about temporal intervals". Communications of the ACM 26(11) pp.832843, Nov. 1983.
Gennari, Rosella. Temporal Reasoning and Constraint Programming: A survey. CWI Quarterly, 11(23):163214. 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. 591640, 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. 373381, 1989.