On redundant topological constraints

DOI10.1016/J.ARTINT.2015.03.010MaRDI QIDQ891795zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Sanjiang Li, Zhiguo Long, Weiming Liu, Matt Duckham, Alan Both

Publication date 17 November 2015

Published in Artificial Intelligence (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1403.0613

zbMATH Keywords

redundancyqualitative spatial reasoningregion connection calculusdistributive subalgebraprime subnetwork

Mathematics Subject Classification ID

Knowledge representation (68T30)

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 RCC5 and RCC8 (two fragments of RCC) as well as other qualitative spatial/temporal calculi has been investigated in depth in the literature. Most of these works focus on the consistency of qualitative constraint networks. In this paper, we consider the important problem of redundant qualitative constraints. For a set $Gamma$ of qualitative constraints, we say a constraint $(xRy)$ in $Gamma$ is redundant if it is entailed by the rest of $Gamma$. A prime subnetwork of $Gamma$ is a subset of $Gamma$ which contains no redundant constraints and has the same solution set as $Gamma$. It is natural to ask how to compute such a prime subnetwork, and when it is unique. In this paper, we show that this problem is in general intractable, but becomes tractable if $Gamma$ is over a tractable subalgebra $mathcalS$ of a qualitative calculus. Furthermore, if $mathcalS$ is a subalgebra of RCC5 or RCC8 in which weak composition distributes over nonempty intersections, then $Gamma$ has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from $Gamma$. As a byproduct, we show that any path-consistent network over such a distributive subalgebra is weakly globally consistent and minimal. A thorough empirical analysis of the prime subnetwork upon real geographical data sets demonstrates the approach is able to identify significantly more redundant constraints than previously proposed algorithms, especially in constraint networks with larger proportions of partial overlap relations.

Recommendations

• Redundancy in logic. I: CNF propositional formulae
• Constraint networks of topological relations and convexity
• Algebraic foundations for qualitative calculi and networks
• On topological consistency and realization
• Collective singleton-based consistency for qualitative constraint networks

Cites work

• scientific article; zbMATH DE number 1149443 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 1487799 (Why is no real title available?)
• scientific article; zbMATH DE number 4185056 (Why is no real title available?)
• A relation-algebraic approach to the region connection calculus
• Algorithms for computing minimal equivalent subformulas
• Boolean connection algebras: A new approach to the Region-Connection Calculus
• Computing the minimal relations in point-based qualitative temporal reasoning through metagraph closure
• Constraint networks of topological relations and convexity
• Convex solutions of RCC8 networks
• Decomposition and tractability in qualitative spatial and temporal reasoning
• Maintaining knowledge about temporal intervals
• Networks of constraints: Fundamental properties and applications to picture processing
• On the complexity of qualitative spatial reasoning: A maximal tractable fragment of the Region Connection Calculus
• Qualitative constraint satisfaction problems: an extended framework with landmarks
• Reasoning about cardinal directions between extended objects
• Reasoning about cardinal directions between extended objects: the NP-hardness result
• Reasoning about temporal relations
• Redundancy in logic. I: CNF propositional formulae
• Region connection calculus: Its models and composition table
• Relation algebras and their application in temporal and spatial reasoning
• Removing propagation redundant constraints in redundant modeling
• Removing redundancy from a clause

Cited in

(4)

• Compact solution representation in qualitative constraint-based reasoning
• Collective singleton-based consistency for qualitative constraint networks: theory and practice
• On prime scenarios in qualitative spatial and temporal reasoning
• scientific article; zbMATH DE number 475268 (Why is no real title available?)

This page was built for publication: On redundant topological constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q891795)