Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis

Abstract

We present a general method for proving tractabi lity of reasoning over disjunctions of jointly exhau st ive a nd pairwise disjoint relations. Examples of these kinds of relations are Allen's temporal interval relations and their spatial counterpart, the RCC8 relations by Randell , Cui, and Cohn. Applying this method does not require d eta il ed knowledge a bout the considered relations; instead, it is rather sufficient to have a subset of the considered set of relations for which path-consistency is known to decide consistency. Using this m et hod , we give a complete class ifi cation of tractability of reasoning over RCC8 by identifying two large n ew maximal tractabl e subsets ~ nd show that these two subsets together with 1{8 , the already known maximal tractabl e subset, are the only such sets for RCC8 that conta in all base relations. We also apply our method to Allen's interval algebra and derive the known maximal tractable subset.