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.

temporal reasoning, relation algebras, S-languages, Lisp