On the Minimal Labeling Problem of Temporal and Spatial Qualitative Constraints

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.