The Interval Algebra (IA) and a subset of the Region Connection Calculus (RCC), namely RCC-8, are the dominant Artificial Intelligence approaches for representing and reasoning about qualitative temporal and topological relations respectively. Such qualitative information can be formulated as a Qualitative Constraint Network (QCN). In this paper, we focus on the minimal labeling problem (MLP) and we propose an algorithm to efficiently derive all the feasible base relations of a QCN. Our algorithm considers chordal QCNs and a new form of partial consistency. Further, the proposed algorithm uses tractable subclasses of relations having a specific patchwork property for which closure under weak composition implies the consistency of the input QCN. Experimentations with QCNs of IA and RCC-8 show the importance and efficiency of this new approach.

Spatial and temporal reasoning is a crucial task for certain Artificial Intelligence applications. In this context, and since two decades, various formalisms representing the information through qualitative constraint networks (QCN) have been proposed. Given a QCN, the main two problems that are facing researchers are: deciding whether this QCN is consistent or not, and, the minimal labeling problem. In this paper, we propose an efficient algorithm aiming at solving the minimal labeling problem. This algorithm is based on subclasses of relations for which the property of closure under weak composition implies the minimality of the QCN.