When tables tell it all

qualitative spatial and temporal reasoning based on linear orderings

Gérard Ligozat

pp. 60-75

in: Daniel D. Montello (ed), Spatial information theory, Berlin, Springer, 2001

Abstract

In [8] Bennett, Isli and Cohn put out the following challenge to researchers working with theories based on composition tables (CT): give a general characterization of theories and relational constraint languages for which a complete proof procedure can be specified by a CT. For theories based on CTs, they make the distinction between a weak, consistency-based interpretation of the CT, and a stronger extensional definition. In this paper, we take up a limited aspect of the challenge, namely, we characterize a subclass of formalisms for which the weak interpretation can be related in a canonical way to a structure based on a total ordering, while the strong interpretations have the property of aleph-zero categoricity (all countable models are isomorphic).Our approach is based on algebraic, rather than logical, methods. It can be summarized by two keywords: relation algebra and weak representation.