
## 6 S. R. Schwer / Temporal Reasoning Without Transitive Tables (Rapport Interne 2004 Lipn/Lcr) 3.3. The Point-Interval Algebra

In order to take into account both instantaneous and durative processes, Vilain provided a model with points and intervals [33]. Figure 5 shows the five situations between a point and an interval.

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

Fig. 5. The 5 situations between a point and an interval
(each point designs a situation)
Besides the two preceding transitivity tables, are needed six more transitivity tables: (i) points/intervals-intervals/points, (ii) points/intervals-intervals/intervals,
(iii) points/points-points/intervals, (iv) intervals/intervals-intervals/points,
(v) intervals/points-points/intervals, (vi) intervals/points-points/points.

## 3.4. Chains Algebras

The T-model of Kandrashina [18] has three qualitative basic notions: the point, the interval and the sequence of intervals. Situations between two sequences of intervals are derived from situations between intervals. Some frequent situations are shown like the one in Figure 6:

## Fig. 6. S1 **Alternates** S2

These objects has been revisited and studied for their own by Ladkin [20] under the name of nonconvex intervals. Ligozat [22] generalized to sequences of points and/or intervals under the name of generalized intervals.

There are 3 situations between two points, 5 between a point and an interval, 13 situations between two intervals, 8989 situations between two sequences of three intervals or two sequences of 6 points. Ladkin [20, Theorem1], proved the number of situations between two chains of intervals is at least exponential in the number of intervals. The exact number of situations between a sequence of p points and a sequence of q points has been provided by [6, p. 83] without doing the connection with Delannoy numbers.

Freksa studied transitivity tables with respect to convex set of intervals [14], Randel & al. [28] have studied transitivity tables for reasoning in both time and space in a more general context, both in order to below the complexity rate of the computations. That was also the aim of Vilain et al. who have studied the fragment of the interval algebra, that can be written without disjunction inside the point algebra, based on the fact that relations between intervals can be translated in terms of their bounds, inside the point algebra. An interval A is a couple of its bounds (a, a**¯) viewed as points they**
can contain or not, with the constraint a < a**¯. Situations between intervals are represented in terms**
of the situations of their bounds:

- A is before B iff a < **a < b <** ¯
¯b
- A meets B iff a < a¯ = b < ¯b
- A overlaps B iff a < b < a <¯
¯b
- A starts iff B a = b < a <¯
¯b
- A during iff b < a < a <¯
¯b
- A finishes iff **b < a <** a¯ = ¯b
- A equals B iff a = b < a¯ = ¯b.

## 4. Qualitative Temporal Objects And Relations In The S-Languages Framework 4.1. Temporal Objects

All temporal items previously reviewed are based on points or maximal convex interval, that is isolated points or pairing points. The idea is to assign an identity to each temporal objects. The set of these identities is the alphabet on which the Slanguages will be written. A temporal object with identity a and p **bounds and/or isolated points is**
depicted by the (S-)word a p**. To distinguish between points and bounds, it is possible to mark the**
right bound of an interval. If one non-marked letter follows a non-marked letter, then the first one depicts a point. For instance the S-word **aaaaaa** ¯ aa¯ a¯
depicts the sequence : point, interval, point, point, interval, interval.