A Tool for Reasoning about Qualitative Temporal Information: the Theory of S-languages with a Lisp Implementation

Irène A. Durand (Université de Bordeaux, France)

Sylviane R. Schwer (Université Paris-Nord, France)

Abstract: Reasoning about incomplete qualitative temporal information is an essential topic inmany artificial intelligence and natural language processing applications. In the domain of natural language processing for instance, the temporal analysis of a text yields a set of temporal relationsbetween events in a given linguistic theory. The problem is first to express events and any possible temporal relations between them, then to express the qualitative temporal constraints (as subsetsof the set of all possible temporal relations) and compute (or count) all possible temporal relations that can be deduced. For this purpose, we propose to use the formalism of S-languages, based onthe mathematical notion of S-arrangements with repetitions [Schwer, 2002]. In this paper, we present this formalism in detail and our implementation of it. We explain why Lisp is adequateto implement this theory. Next we describe a Common Lisp system SLS (for S-LanguageS)which implements part of this formalism. A graphical interface written using McCLIM, the free implementation of the CLIM specification, frees the potential user of any Lisp knowledge. Fullydeveloped examples illustrate both the theory and the implementation.

Keywords: Lisp, S-languages, relation algebras, temporal reasoning

Categories: F.4, I.1.1, I.2.4