Allen’s temporal algebra

Syntax

Symbols

We define an infinite set E whose members are called events and the set R = {b, bi, m, mi, o, oi, s, si, d, di, f, fi, eq} disjoint from E whose members are called temporal relations.

Symbols of Allen

The symbols of Allen are Sym_Allen = E ⋃ R.

As with propositions in propositional logic, we will write distinct events with distinct sequences of latin characters like so: WorldWarTwo, MacronPresidency, etc.

Each temporal relation has a name that helps understanding its meaning. The table below informally explains the symbols:

Temporal relations

Symbol	Name	Note
b	before	a first event happens completely before a second one starts
bi	after	the inverse of before (i.e., a first event happens entirely after a second one ends)
m	meets	a first event stops exactly when a second one starts
mi	met by	the inverse of meets (a first event starts exactly when a second one ends)
o	overlaps	a first event occurs before and after a second one starts, and ends before the second one ends
oi	overlapped by	the inverse of overlaps (i.e., a first event occurs before and after a second one ends, and starts after the second one starts)
s	starts	a first event starts at the same time as a second one but ends before the second one
si	started by	the inverse of starts (i.e., a first event starts at the same time as a second one but ends after the second one)
d	during	a first event occurs entirely while a second event is occurring
di	contains	the inverse of during (i.e., a first event occurs before a second one starts and ends after the second ends
f	finishes	a first event stops at the same time as a second event, but starts after the second
fi	finished by	the inverse of finishes (i.e., a first event stops at the same time as a second one, but starts before the second)
eq	equals	two events have the same temporal coverage

Formulas

formulas of Allen

The set For_Allen of Allen formulas is defined as follows: for all events e₁, e₂ ∈ E, and all a temporal relation r ∈ R, e₁ r e₂.

Note that we use a light shading on formulas in order to clearly distinguish them from other syntactic constructs.

WorldWarII b BushJrPresidency

WorldWarI o SpanishFluOutbreak

Semantics

Interpretations

Interpretations in Allen

An interpretation in Allen is a pair (Δ, 𝓘_s, 𝓘_e) such that:

• Δ is a totally ordered set with a strict order relation <, whose elements are called instants;
• 𝓘_s : E ⟶ Δ;
• 𝓘_e : E ⟶ Δ;
• for all e ∈ E, 𝓘_s(e) < 𝓘_e(e).

Satisfaction relation

Satisfaction relation in Allen

For e₁, e₂ ∈ E, an interpretation (Δ, 𝓘) in Allen satisfies:

• e₁ b e₂ if and only if 𝓘_e(e₁) < 𝓘_s(e₂);
• e₁ bi e₂ if and only if 𝓘_e(e₂) < 𝓘_s(e₁);
• e₁ m e₂ if and only if 𝓘_e(e₁) = 𝓘_s(e₂);
• e₁ mi e₂ if and only if 𝓘_e(e₂) = 𝓘_s(e₁);
• e₁ o e₂ if and only if 𝓘_s(e₁) < 𝓘_s(e₂) and 𝓘_e(e₁) < 𝓘_e(e₂);
• e₁ oi e₂ if and only if 𝓘_s(e₂) < 𝓘_s(e₁) and 𝓘_e(e₂) < 𝓘_e(e₁);
• e₁ s e₂ if and only if 𝓘_s(e₁) = 𝓘_s(e₂) and 𝓘_e(e₁) < 𝓘_e(e₂);
• e₁ si e₂ if and only if 𝓘_s(e₂) = 𝓘_s(e₁) and 𝓘_e(e₂) < 𝓘_e(e₁);
• e₁ d e₂ if and only if 𝓘_s(e₂) < 𝓘_s(e₁) and 𝓘_e(e₁) < 𝓘_e(e₂);
• e₁ di e₂ if and only if 𝓘_s(e₁) < 𝓘_s(e₂) and 𝓘_e(e₂) < 𝓘_e(e₁);
• e₁ f e₂ if and only if 𝓘_s(e₂) < 𝓘_s(e₁) and 𝓘_e(e₁) = 𝓘_e(e₂);
• e₁ fi e₂ if and only if 𝓘_s(e₁) < 𝓘_s(e₂) and 𝓘_e(e₂) = 𝓘_e(e₁);
• e₁ eq e₂ if and only if 𝓘_s(e₁) = 𝓘_s(e₂) and 𝓘_e(e₁) = 𝓘_e(e₂).

Table 2 presents a graphical view of the relations between events, presented as intervals on a timeline.

Allen’s interval relations depicted geometrically as relations between parallel line segments

Relation	Inverse relation	Graphical representation
X b Y	Y bi X
X m Y	Y mi X
X o Y	Y oi X
X s Y	Y si X
X d Y	Y di X
X f Y	Y fi X
X eq Y	Y eq X

Extensions to sets of relations

Instead of defining temporal relations as a single possible relation (strictly defining how the starts and ends of the events relate relative to the other), we can extend Allen to express a set of alternative temporal relations between pairs of events. We define the extension Allen⁺ = (Sym_Allen⁺, For_Allen⁺, Int_Allen⁺, ⊨_Allen⁺) as follows:

• Sym_Allen⁺ = Sym_Allen ⋃ {‘{’, ‘}’, ‘,’};
• for e₁, e₂ ∈ E and a tuple (r₁, …, r_n) ∈ Rⁿ, e₁ {r₁, …, r_n} e₂ ∈ For_Allen⁺;
• Int_Allen⁺ = Int_Allen;
• for 𝓘 ∈ Int_Allen⁺ and φ = e₁ {r₁, …, r_n} e₂ ∈ For_Allen⁺, 𝓘 ⊨_Allen⁺ φ if and only if 𝓘 ⊨_Allen e₁ r_i e₂ for some i ∈ {1, …, n}.

Properties of Allen’s algebra

The entailment problem for Allen⁺ is NP-complete with respect to the size of the input theory.