S. R. Schwer / Temporal reasoning without transitive tables **(Rapport interne 2004 LIPN/LCR) 5**
for convex intervals (Allen), for points, for points and convex intervals: knowing an atomic relation between objets A and B **and an atomic relation**
between objects B and C**, derive the possible - or**
other said not prohibited - relations between objects A and C.

Cohn et al. **[28] have studied transitivity tables**
for reasoning in both time and space in a more general context. They noted the difficulty to build such secure transitivity tables.

## 3.1. The Point Algebra.

The three situations are the three basic temporal relations: before <**, equals = and after** > as shown in Figure 1. The set of point qualitative Fig. 1. situations of the black point with respect to the white point.

$$\begin{array}{l l l l}{{}}&{{}}&{{}}&{{\bullet}}\\ {{}}&{{\odot}}&{{}}&{{\odot}}\\ {{}}&{{<}}&{{}}&{{=}}\end{array}\qquad{\begin{array}{l l l l}{{}}&{{}}&{{}}&{{\odot}}\\ {{}}&{{}}&{{}}&{{}}\\ {{}}&{{}}&{{}}&{{>}}\end{array}$$

temporal binary relations is the set : {**<, >,** =, 6
, >, 6=, ⊥, ⊤}, where ⊥ **is the empty relation (no**
feasible relation) and ⊤ **the universal relation (any**
relation is feasible). The transitive table is given in Figure 2

![0_image_2.png](0_image_2.png)

Fig. 2. point transitivity table For instance, if A < B and B > C **then** A⊤C.

## 3.2. The Interval Algebra.

In Figure 3, we recall the thirteen situations between two intervals studied by Allen [1].

The transitivity table is given in Table 4 where1:
✷ = ⊤, that is there is no constraint, every situa1**The notation is taken, whenever possible, from Delannoy paths draw as kind of greek letters on the chess, with**
the following convention: Upper case for 5-subsets, lower case for 3-subsets

## Rel Or Rel∼

equals(=) OR equals(=)

![0_image_0.png](0_image_0.png)

started-by (s
∼) OR **starts** (s)
contains(d
∼) OR **during** (d)
finished-by (f
∼) OR **finishes** (f)
overlaps (o)OR**overlapped-by**(o
∼)
meets (m) OR **met-by** (m∼)
before (<) OR **after** (>)
Fig. 3. the set of 13 situations between two intervals on line tion is allowed,
✸ = ⊤−{<, m, m∼, >}**, which means that the two**
intervals intersects on an interval, this is exactly what Kamp named the overlapping2**relation** ◦ on two processes [17] and Freksa the contemporary relation [14], Γ
∼ = {<, m, o, s, d}, that is the relation **begin before**, Λ = {<, m, o, d∼, f ∼}, that is the **relation end after**
α = {**<, m, o**}, δ
∼ = {**o, s, d**}, ρ
∼ = {o
∼**, d, f**},
sˆ = {s, =, s∼},
ˆf = {f, =, f ∼}
and using the following property:
∀A ⊆ ⊤, x ∈ **A iff x**∼ ∈ A∼.

![0_image_1.png](0_image_1.png)

Fig. 4. interval transitivity table