Spatial and temporal reasoning: beyond Allen's calculus

Issue title: Spatial and Temporal Reasoning

Article type: Research Article

Authors: Ligozat, Gérard | Mitra, Debasis | Condotta, Jean‐François

Affiliations: LIMSI‐CNRS, Université Paris‐Sud, 91403 Orsay, France E‐mail: ligozat@limsi.fr | Department of Computer Sciences, Florida Institute of Technology, Melbourne, FL 32901, USA E‐mail: dmitra@cs.fit.edu | Centre de Recherche en Informatique de Lens, Université d'Artois, 62307 Lens, France E‐mail: condotta@cril.univ‐artois.fr

Abstract: Many formalisms for qualitative spatial and temporal reasoning fit into a pattern exemplified by Allen's temporal interval calculus. Constraint‐based reasoning using Allen's calculus can benefit from some of its main properties: (a) the underlying constraint algebra is a relation algebra, in Tarski's sense; (b) testing path‐consistency is a complete method for testing consistency for well‐determined subclasses of relations; (c) atomic path‐consistent networks are consistent and determine unique qualitative configurations; (d) the first order theory associated to the calculus is aleph‐zero categorical. When considering analogous calculi, many of the properties mentioned above no longer hold. The main object of this paper is to examine some of the new questions which arise. In order to do so, we use the idea of weak representations of the algebras as a unifying concept.

Keywords: Qualitative spatial and temporal reasoning, relation algebra, tractability, weak representation

Journal: AI Communications, vol. 17, no. 4, pp. 223-233, 2004