计算机科学学院七十周年校庆系列学术报告--On Redundant Topological Constraints

讲座内容：The Region Connection Calculus (RCC) isa well-known calculus for representing part-whole and topological relations. Itplays 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 considerthe 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 isover 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 identifya sufficient condition for a path-consistent network being minimal.