RCC8 binary constraint network can be consistently extended

Prof. Dr. Sanjiang Li

The RCC8 constraint language developed by Randell et al. has been popularly adopted by the Qualitative Spatial Reasoning and GIS communities. The recent observation that RCC8 composition table describes only weak composition instead of composition puts under suspicion Renz and Nebel's computational complexity results of reasoning with RCC8.

This paper shows that any consistent RCC8 binary constraint network (BCN) can be consistently extended. Given three RCC8 relations R,S,T and an RCC8 BCN Theta, and suppose T is contained in the weak composition of R and S, (x T y) is in the BCN Theta, and z is a fresh variable. This means that we can add two new constraints (x R z) and (z S y) to Theta without changing the consistency of the BCN. The result guarantees the applicability of one key technique (Theorem 5) to RCC8 used in the work of Renz and Nebel (Artificial Intelligence, 108:69-123, 1999), which allows the transfer of tractability of a set of RCC8 relations to its closure under composition, intersection, and converse.