---
title: "Maximal Tractable Fragments of the Region Connection Calculus: A Complete Analysis"
authors:
  - "Jochen Renz"
doi: ""
url: "https://ijcai.org/proceedings/1999/65"
pdf: "https://ijcai.org/proceedings/1999/0065.pdf"
venue: "Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence"
year: 1999
pages: "448-454"
track: "Constraint Satisfaction"
keywords:
---

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

Jochen Renz

*Proceedings of the Sixteenth International Joint Conference on Artificial Intelligence*, pages 448-454.

## 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.