# Temporal Reasoning Without Transitive Tables

Sylviane R. Schwer LIPN UMR 7030 (Universit´e Paris 13 et CNRS)
sylviane.schwer@lipn.univ-paris13.fr Representing and reasoning about qualitative temporal information is an essential part of many artificial intelligence tasks. Lots of models have been proposed in the litterature for representing such temporal information. All derive from a point-based or an interval-based framework. One fundamental reasoning task that arises in applications of these frameworks is given by the following scheme: given possibly indefinite and incomplete knowledge of the binary relationships between some temporal objects, find the consistent scenarii between all these objects. All these models require transitive tables - or similarly inference rules - for solving such tasks.

In [30], we have defined an alternative model, renamed in [31] S-languages - for Set-languages - to represent qualitative temporal information, based on the only two relations of **precedence** and **simultaneity**. In this paper, we show how this model enables to avoid transitive tables or inference rules to handle this kind of problem.

Keywords: Temporal reasoning, formal languages, constraints satisfaction.

## 1. Introduction

Representing and reasoning about qualitative temporal information is an essential part of many artificial intelligence tasks. These tasks appear in such diverse areas as natural language processing, planning, plan recognition, and diagnosis. Allen
[1,2] has proposed an interval algebra framework and Vilain and Kautz [34] have proposed a point algebra framework for representing such qualitative information. All models that have been proposed afterwards in the litterature derive from these two frameworks. Placing two intervals on the Timeline, regardless of their length, gives thirteen relations, known as Allen's [2] relations. Vilain [33]
provided relations for points and intervals, Kandrashina [18] provided relations for points, intervals and chains of intervals. Relations between two chains of intervals have been studied in depth by Ladkin who named them non convex intervals [20]. Al-Khatib [19] used a matricial approach. Ligozat [22] has studied relations between chains of points, named generalized intervals.

One fundamental reasoning task that arises in applications in these frameworks is given by the following scheme: given possibly indefinite and incomplete knowledge of the relationships between some temporal objects, find the consistent scenarii between all these objects. All these models have in common that the representations of temporal information are depicted as sets of binary relationships and are viewed as binary constraint networks. The reasoning is then based on transitive tables that describe the composition of any two binary relations. All these models require transitive tables - or similarly inference rules - for solving such tasks. The logical approach of the I.A.

community explains this fact.

The framework of formal languages, inside which the model of S-languages has been proposed [30, 31], provides the same material both for expressing the temporal objects and the n-ary relationships between them. The reasoning is based on three natural extensions of very well-known rational operations on languages: the intersection, the shuffle and the projection. More precisely, we have shown in [31] that binary relations between two generalized intervals are in a natural correspondence with S-languages that express Delannoy paths of order 2. By the way, we provide to Henry Delannoy
(1833-1915) a large domain of applications (though unexpected) of his theory of minimal paths of the queen from one corner to any other position on a chess-board [9].

The main idea for using formal languages for temporal representation and reasoning is that a word can be viewed as a line, with an arrow from 1