| Abstract: | The Region Connection Calculus (RCC) is a well-known calculus for representing part-whole and topological relations. It plays an important role in qualitative spatial reasoning, geographical information science, and ontology. The computational complexity of reasoning with RCC has been investigated in depth in the literature. Most of these works focus on the consistency of RCC constraint networks. In this talk, we consider the important problem of redundant RCC constraints. For a set N of RCC constraints, we say a constraint (x R y) in N is redundant if it can be entailed by the rest of N, i.e., removing (x R y) from N will not change the solution set of N. A prime subnetwork of N is a subset of N which contains no redundant constraints but has the same solution set as N. It is natural to ask how to compute such a prime subnetwork, and when it is unique. In this talk, we show that this problem is in general intractable, but becomes tractable if N is over a tractable subclass S of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can further show that N has a unique prime subnetwork, which is obtained by removing all redundant constraints simultaneously from N. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal. |
