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:
Full metadata record
Files in This Item:
Filename Description Size
Thumbnailprime_network-general_KR.pdfAccepted Manuscript version1.56 MB
Adobe PDF
Thumbnail[KR14]-Prime.pdf Published version1.55 MB
Adobe PDF
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: