Optimisation des réseaux de contraintes qualitatives temporelles

Loading...
Thumbnail Image

Date

2017

Journal Title

Journal ISSN

Volume Title

Publisher

UMMTO

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.

Description

48 f.; ill. : 30 cm + (CD-Rom)

Keywords

RCQT : réseau de contraintes qualitatives temporelles, IA : algèbre des points, PA : algèbre des intervalles, MinCons : cohérence minimale

Citation