On redundant topological constraints
- Publication Type:
- Conference Proceeding
- 14th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2014, 2014, pp. 618 - 621
- Issue Date:
Copyright Clearance Process
- Recently Added
- In Progress
- Closed Access
This item is closed access and not available.
Copyright © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 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 paper, we consider the important problem of redundant RCC constraints. For a set Γ of RCC constraints, we say a constraint (xRy) in Γ is redundant if it can be entailed by the rest of Γ. A prime subnetwork of Γ is a subset of Γ which contains no redundant constraints but has the same solution set as Γ. It is natural to ask how to compute a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if S is over a tractable subclass of RCC. If S is a tractable subclass in which weak composition distributes over non-empty intersections, then we can show that Γ has a unique prime network, which is obtained by removing all redundant constraints from Γ. As a byproduct, we identify a sufficient condition for a path-consistent network being minimal.
Please use this identifier to cite or link to this item: