Weak composition for qualitative spatial and temporal reasoning
Date
2005
Authors
Renz, Jochen
Ligozat, Gerard
Journal Title
Journal ISSN
Volume Title
Publisher
Springer
Abstract
It has now been clear for some time that for many qualitative spatial or temporal calculi, for instance the well-known RCC8 calculus, the operation of composition of relations which is used is actually only weak composition, which is defined as the strongest relation in the calculus that contains the real composition. An immediate consequence for qualitative calculi where weak composition is not equivalent to composition is that the well-known concept of pathconsistency is not applicable anymore. In these cases we can only use algebraic closure which corresponds to applying the path-consistency algorithm with weak composition instead of composition. In this paper we analyse the effects of having weak compositions. Starting with atomic CSPs, we show under which conditions algebraic closure can be used to decide consistency in a qualitative calculus, how weak consistency affects different important techniques for analysing qualitative calculi and under which conditions these techniques can be applied. For our analysis we introduce a new concept for qualitative relations, the "closure under constraints". It turns out that the most important property of a qualitative calculus is not whether weak composition is equivalent to composition, but whether the relations are closed under constraints. All our results are general and can be applied to all existing and future qualitative spatial and temporal calculi. We close our paper with a road map of how qualitative calculi should be analysed. As a side effect it turns out that some results in the literature have to be reconsidered.
Description
Keywords
Keywords: Algebra; Algorithms; Computer science; Constraint theory; Algebraic closure; Path consistency algorithm; Weak composition; Formal logic
Citation
Collections
Source
Proceedings of International Conference on Principles and Practice of Constraint Programming (CP 2005)
Type
Conference paper
Book Title
Entity type
Access Statement
License Rights
Restricted until
2037-12-31
Downloads
File
Description