Optimisation des réseaux de contraintes qualitatives temporelles

Abstract

Dans ce travail, nous montrons que MinCons est NP-complet pour PA malgré le fait que le problème de cohérence est polynomial pour ce calcul. Moins surprenant, MinCons est également Np-complet pour IA dans le cas général, mais est également NP-complet pour certaines sous-classes pour lesquelles le problème de cohérence est connu pour être résoluble. Dans cet esprit, nous nous concentrons sur les sous-classes des relations convexes de PA et IA et montrons que pour ces cas particuliers, MinCons est polynomial. Nous définissons, pour les RCQT convexes, une méthode polynomiale pour extraire des scénarios compacts correspondant à des éléments minimaux d'ordres partiels particuliers.