
$$4$$

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

$\text{S.R.Schwer/Temporal reasoning with}$  . 
$$D(p_{1},\ldots,p_{n})=\sum_{{\mathcal{P}}r e d(p_{1},\ldots,p_{n})}D_{n}({\widetilde{p_{1}}},\ldots,{\widetilde{p_{n}}})$$

where for p > 0), pe = {p, p − 1}; e0 = {0} and Pred((p1, · · · , pn)) = {(pe1, · · · , pfn)}−{(p1, · · · , pn)}.

In particular D(p, q)=D(p, q − 1) + D(p − 1, q −
1) + D(p − 1, q) with the initial steps D(0, **0) =** D(0, 1) = D(1, **0) = 1.**
Like Pascal's table for computing binomial numbers, there is a Delannoy table for computing Delannoy numbers, given in Table 1.

| p   | q 0 1                                                | 2                        | 3             | 4    | 5     | 6    | 7    | 8   |
|-----|------------------------------------------------------|--------------------------|---------------|------|-------|------|------|-----|
| 0   | 1 1                                                  | 1                        | 1             | 1    | 1     | 1    | 1    | 1   |
| 1   | 1 3                                                  | 5                        | 7             | 9    | 11    | 13   | 15   | 17  |
| 2   | 1 5 13                                               | 25                       | 41            | 61   | 85    | 113  | 145  |     |
| 3   | 1 7                                                  | 25                       | 63            | 129  | 231   | 377  | 575  | 833 |
| 4   | 1 9                                                  | 41                       | 129 321       | 681  | 1289  | 2241 | 3649 |     |
| 5   | 1 11 61                                              | 231                      | 681 1683 3653 | 7183 | 13073 |      |      |     |
| 6   | 1 13 85                                              | 377 1289 3653 8989 19825 | 40081         |      |       |      |      |     |
| 7   | 1 15 113 575 2241 7183 19825 48639 108545            |                          |               |      |       |      |      |     |
| 8   | 1 17 145 833 3649 13073 40081 108545 265729          |                          |               |      |       |      |      |     |
| 9   | 1 19 181 1159 5641 22363 75517 224143 598417 Table 1 |                          |               |      |       |      |      |     |

D(p, q**) are the well-known Delannoy numbers**

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

[9,35,32] that enumerate Delannoy paths in a (p,q)-rectangular chessboard. A Delannoy path is given as a path that can be drawn on a rectangular grid, starting from the southwest corner, going to the northeast corner, using only three kinds of elementary steps: north, east, and northeast**. Hence they are minimal paths with diagonal**
steps. The natural correspondence between (p,q)-
Delannoy paths and L(p, q) on the alphabet {**a, b**}
is: the S-letter a corresponds to a north**-step, the**
S-letter b to a east**-step and the S-letter** a b to north-east**-step.**

## 2.2.3. Projection

We extend the well-known notion of projection in formal languages theory to S-languages.

The aim is to be able to erase all occurrences of some letters in an S-word and having as results a new S-word. The problem is how to handle an S-letter with all its letters erased. For that purpose we set: let X **be an alphabet and** f ∈ Xb
∗

,
Xf = {x ∈ X|kfkx 6= 0}.

Definition 2.4 Let X **be an alphabet and** Y ⊆ X.

The S-projection from Xb
∗

to Yb
∗

is a monoid morphism π X
Y
defined by the image of the S-letters: for s ⊂ X**, its image is** π X
Y
(s) = s ∩Y if this intersection is not empty, ε **if not.**
The projection on Y of an S-word f **is denoted** f|Y
instead of π X
Y
(f).

Example 2 (Example 1 continued) Let f = a b cba a c c a b a   a b c   aaaa, - f|{a} = aaaaaaaaaa, - f|{b}=bbbb, - f|{c}=cccc, - f|{a,b} = a b baa a b a a b aaaa, - f|{b,c} = bcbccb bc , - f|{a,c}= aca a c caa a c aaaa, - f|{a,b,c}=f.

## 3. Qualitative Temporal Objects And Relations In The Binary Algebra And Their Transitivity Tables

We examine qualitative temporal objects and relations inside the framework of relational algebra, as Ladkin and Maddux initiated it [21]. We recall the usual qualitative temporal binary algebra: the point algebra, the interval algebra [2], the pointinterval algebra [33,34], chains algebra.

In this paper, we use the term situation **for the**
description of a unique temporal relation (complete information) between objects, which is sometimes called an atomic relation.

Let us recall the principia of transitivity table.

Given a particular theory Σ supporting a set of mutually exhaustive and pairwise disjoint dyadic situations, three individuals, a, b and c **and a pair**
of dyadic relations R1 and R2 **selected from Σ such**
that R1(a, b) and R2(b, c**), the transitive closure**
R3(a, c) represents a disjunction of all the possible dyadic situations holding between a and c in Σ. Each R3(a, c**) result can be represented as one**
entry of a matrix for each R1(a, b) and R2(b, c) ordered pair. If there are n dyadic situations supported by Σ, then there will be n×n **entries in the**
matrix. This matrix is a transitivity table. Transitive tables for binary situations have been written