Consistency of Triangulated Temporal Qualitative Constraint Networks

Abstract

In this paper, we introduce for the qualitative constraint networks (QCNs) a new consistency: the partial weak composition consistency. The partial weak composition consistency, similarly to the partial path-consistency, considers triangles of a graph and corresponds to the weak composition consistency restricted to these triangles. We show that for the pre-convex QCNs of the Interval Algebra (IA), the partial weak composition consistency with respect to a triangulation of the graph of constraints is sufficient to decide the consistency problem. From this result, we propose an algorithm allowing to solve QCNs of IA. The experiments that we have conducted show the interest of this algorithm to solve the consistency problem of the QCNs of IA.