Décompositions structurelles et sémantiques Rapport préliminaire

Philippe Jégou 1 Cyril Terrioux 1
1 COALA - COntraintes, ALgorithmes et Applications
LIS - Laboratoire d'Informatique et Systèmes
Résumé : Dans le cas des modèles graphiques, même les plus simples comme les CSP (réseaux de contraintes), les dé-compositions généralement proposées dans la littérature s'intéressent pour l'essentiel à la structure. Cela étant, afin de mieux appréhender un problème dans sa globalité, il serait souhaitable aussi de prendre en compte sa séman-tique, au sens des domaines des variables, et des relations de compatibilité qui leur sont associées via les contraintes. Dans cette note, il est proposé une nouvelle approche de la problématique qui prend justement en compte ces deux aspects pour définir une nouvelle forme de décom-position et son paramètre associé. L'une des ambitions d'une telle démarche et qui peut d'ailleurs constituer un réel défi pour la communauté, est de dépasser les limites actuellement posées par les décompositions arbo-rescentes de graphes de tree-width (ou largeur) bornée. On montre ainsi que le paramètre que nous proposons minore systématiquement la tree-width d'un réseau de contraintes binaires (cf. théorème 1) qui constitue "la" borne fondamentale actuelle pour le traitement de nom-breux problèmes combinatoires, dès lors qu'ils s'expriment en termes de graphes et qu'il s'agit de les résoudre par des approches fondées sur leur structure. Toutefois, si ce premier résultat semble démontrer la pertinence d'une telle approche, cette contribution doit être considérée comme une contribution très préliminaire à une éventuelle nouvelle voie de recherches.
Document type :
Conference papers
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-amu.archives-ouvertes.fr/hal-02162848
Contributor : Cyril Terrioux <>
Submitted on : Saturday, June 22, 2019 - 10:56:26 PM
Last modification on : Thursday, June 27, 2019 - 1:40:32 AM

File

JFPC_2019_paper_25.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02162848, version 1

Collections

Citation

Philippe Jégou, Cyril Terrioux. Décompositions structurelles et sémantiques Rapport préliminaire. Actes des 15èmes Journées Francophones de Programmation par Contraintes (JFPC), Jun 2019, Albi, France. pp.3-6. ⟨hal-02162848⟩

Share

Metrics

Record views

42

Files downloads

5