S. R. Schwer / Temporal reasoning without transitive tables **(Rapport interne 2004 LIPN/LCR) 7**

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

Fig. 7. A relation between 3 chains of intervals

## 4.2. Temporal Relations

A relation between n temporal items, using alphabet X = {x1, · · · , xn}**, is an S-word on** Xb∗ =
2 X − ∅ **that describes exactly the situation of the**
points on the timeline, described by the relation. For instance Example 3 (Examples 1 and 2 continued) Let A, B, C three temporal items as depicted in figure 7.

On the alphabet X = {a, b, c}**, item A is written**
aaaaaaaaaa, item B bbbb and item C cccc. The situation between them is given by the S-word f of Example 1, that is

$$f=\left\{{a\atop b}\right\}c b a\left\{{a\atop c}\right\}c\left\{{a\atop b}\right\}a\;.$$

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

$$\left\{\begin{array}{l l}{a a a a.\ H e n c e,\ i n t}\\ {}\end{array}\right.$$

Example 2, we have computed:
- f|{a}**, which is item A,**
- f|{b}**, which is item B,** - f|{c}**, which is item C,**
- f|{a,b}**, which is the relation between A and B,** - f|{b,c}**, which is the relation between B and C,** - f|{a,c}**, which is the relation between A and C,** - f|{a,b,c}**, which is the relation between A, B and**
C.
The following theorem [31] is the most important for our purpose:
Theorem 4.1 For any integer n ≥ 1, let T1, · · · , Tn be n temporal items, Xn = {x1, . . . , xn} **be an**
alphabet and x p1
, · · · , xpn **– writing** x n **the word**
x . . . x | {z }
ntimes
- their temporal words on X. Let us denote by Π(p1, . . . , pn) **the set of all n-ary situations**
among T1, · · · , Tn, L(p1, · · · , pn) **is its corresponding language.**
In dimension 2, it is obvious to see that there is a natural correspondence between L(p, q**) and**
Delannoy paths in a (p,q)-rectangular chessboard.

The correspondence between interval situations, L(p, q**) and (2,2)-Delannoy paths is shown in Figure 9, inside the N¨okel Lattice [25].**
The arrow means, for S-words, the Thue rewriting rules [3] ab →
a b
→ ba**, which is exactly the**

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

Point lattice as we can see it in Figure 8. Autebert et al. have proved [4] that the S-language L(**p, q**) on the alphabet {a, b} **(that is any set of situations**
between a sequence of p **points and a sequence of**
q points or Ligozat's Π(p, q**) set [22]) can be generated from the single S-word** a pb q **and these Thue**
rewriting rules. They also rigorously proved that these rules make the (p,q)Parikh vector S-language to be a distributive lattice. They also characterize the subset of union**-irreducible S-words, which is**
the lattice of ideals of the language :
{a p−1b q−1| p > 0, q}||{c**} ∪ {**a p−kb la kb q−l| 0 <
l ≤ q, 0 < k ≤ p}**. Its cardinality is 2**pq.

Autebert and Schwer [5] generalized the results to the n-ary case, proving that L(p1, · · · , pn**), with**
the following Thue rewriting rule is also a lattice, but not distributive because not modular, as soon as n ≥ **3 like Figure 10 shows it. Given an arbitrary**
order over the letters of X by a1 < a2 < · · · < an, this induces over the S-letters a partial order P <
Q ⇐⇒ [∀x ∈ P, ∀y ∈ Q : x < y**]. Then the Thue**
system denoted −→ on Xb∗**, by the following:**
∀P, Q, R ∈ Xb such that P < Q and R = P ∪ Q,
set P Q −→ R and R −→ QP.

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

