Redundancy checking is an important task in the research of knowledge representation and reasoning. In this paper, we consider redundant qualitative constraints. For a set ? of qualitative constraints, we say a constraint ( x R y ) in ? is redundant if it is entailed by the rest of ?. A prime subnetwork of ? is a subset of ? which contains no redundant constraints and has the same solution set as ?. It is natural to ask how to compute such a prime subnetwork, and when it is unique. We show that this problem is in general intractable, but becomes tractable if ? is over a tractable subalgebra S of a qualitative calculus. Furthermore, if S is a subalgebra of the Region Connection Calculus RCC8 in which weak composition distributes over nonempty intersections, then ? has a unique prime subnetwork, which can be obtained in cubic time by removing all redundant constraints simultaneously from ?. As a by-product, we show that any path-consistent network over such a distributive subalgebra is minimal and globally consistent in a qualitative sense. 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.
The property of distributivity was first used by van Beek @cite_52 for IA, but the notion of distributive subalgebra is new. It is not difficult to show that PA , IA, RCC5 and RCC8 all have two maximal distributive subalgebras (see for maximal distributive subalgebras of RCC5 8). Very interestingly, the two maximal distributive subalgebras of IA are exactly the subalgebras @math and @math discussed in @cite_16 , where Amaneddine and Condotta proved that @math and @math are the only maximal subalgebras of IA over which path-consistent networks are globally consistent. For RCC8, the maximal distributive subalgebra @math we identify in turns out to be the class of convex RCC8 relations found in @cite_18 , where Chandra and Pujari proved that path-consistent networks over @math are minimal. In we find another maximal distributive subalgebra for RCC8, which contains 64 relations. Furthermore, we also show that every path-consistent constraint network @math over a distributive subalgebra is weakly globally consistent and minimal. This has not been studied for RCC5 8 before.
@cite_18 @cite_16 @cite_52
2164745460 50869828 159907047
The research in qualitative reasoning and in spatial CSP is always investigated in the backdrop of its temporal counterpart - qualitative temporal reasoning and TCSP. Unlike the case of interval algebra (IA), the composition table of RCC, IA's so-called spatial counterpart, is in general neither complete nor extensional, the compositional consistency can be still a valid reasoning mechanism. Even in such a restricted situation, many of the known properties of IA have not been investigated for validity in the context of RCC. We address, in this paper two such properties-convexity and minimality. The importance of minimality cannot be underestimated as in a minimal network every label is feasible and hence determining all the consistent scenarios can be accomplished very efficiently. It is known that path consistency does not yield a minimal network for tractable classes of RCC-8. We represent RCC-8 relations as a partially ordered set and exploit the properties of partial ordering to derive very interesting theoretical results. We show here that there exists a convex class of relations of RCC-8 for which path consistency yields a minimal network. Our results are very important as it gives a sufficient condition for minimality and useful to generate all consistent scenarios whenever compositional consistency is a valid reasoning mechanism We study in this paper the problem of global consistency for qualitative constraints networks (QCNs) of the Point Algebra (PA) and the Interval Algebra (IA). In particular, we consider the subclass @math corresponding to the set of relations of PA except the relations ,= , and the subclass @math corresponding to pointizable relations of IA one can express by means of relations of @math . We prove that path-consistency implies global consistency for QCNs defined on these subclasses. Moreover, we show that with the subclasses corresponding to convex relations, there are unique greatest subclasses of PA and IA containing singleton relations satisfying this property. We consider a representation for temporal relations between intervals introduced by James Allen, and its associated computational or reasoning problem: given possibly indefinite knowledge of the relations between some intervals, how do we compute the strongest possible assertions about the relations between some or all intervals. Determining exact solutions to this problem has been shown to be (almost assuredly) intractable. Allen gives an approximation algorithm based on constraint propagation. We giv e new approximation algorithms, examine their effectiveness, and determine under what conditions the algorithms are exact.