AAAI Publications, Twelfth International Conference on the Principles of Knowledge Representation and Reasoning

Font Size: 
A Class of df-Consistencies for Qualitative Constraint Networks
Jean-François Condotta, Christophe Lecoutre

Last modified: 2010-04-27


In this paper, we introduce a new class of local consistencies, called df-consistencies, for qualitative constraint networks. Each consistency of this class is based on weak composition and a mapping f that provides a covering for each relation of the considered qualitative calculus. We study the connections existing between some properties of the introduced mappings and the relative inference strength of df-consistencies. The consistency obtained by the usual closure under weak composition corresponds to the weakest element of the class, whereas df-consistencies stronger than weak composition open new promising perspectives. Interestingly, the class of df-consistencies is shown to form a complete lattice where the partial order denotes the relative strength of every two consistencies. We also propose a generic algorithm that allows us to compute the closure of qualitative constraint networks under any "well-behaved" consistency of the class. The experimentation that we have conducted on qualitative constraint networks from the Interval Algebra shows the interest of these new local consistencies, in particular for the consistency problem.


qualitative constraint networks; local consistency

Full Text: PDF