Un solveur de contraintes basé sur les domaines abstraits

Marie Pelleau 1 Antoine Miné 2, 3 Charlotte Truchet 1 Frédéric Benhamou 4
1 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
3 ABSTRACTION - Abstract Interpretation and Static Analysis
DI-ENS - Département d'informatique de l'École normale supérieure, Inria Paris-Rocquencourt, CNRS - Centre National de la Recherche Scientifique : UMR 8548
Résumé : Dans cet article, nous utilisons des techniques de l'interpréation abstraite (une théorie d'approximation des sémantiques) dans le cadre de la programmation par contraintes (basée sur la logique du premier ordre qui permet de résoudre des problèmes combinatoires). Nous mettons en évidence certains liens et différences entre ces domaines de recherches : tous deux calculent itérativement des points fixes mais emploient des extrapolations et stratégies de raffinement différentes. De plus, nous pouvons mettre en correspondance les consistances en programmation par contraintes et les domaines abstraits non relationnels. Nous utilisons ensuite ces correspondances pour construire un solveur de contraintes abstrait qui s'appuie sur des techniques d'interprétation abstraite (comme les domaines relationnels) pour aller au-delà des solveurs classiques. Les résultats expérimentaux obtenus avec notre prototype sont encourageants.
Type de document :
Communication dans un congrès
9èmes Journées Francophones de Programmation par Contraintes, Jun 2013, Aix-en-Provence, France. pp.259-268, 2013
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00925430
Contributeur : Antoine Miné <>
Soumis le : mercredi 8 janvier 2014 - 09:56:20
Dernière modification le : lundi 16 juillet 2018 - 11:06:02
Document(s) archivé(s) le : mardi 8 avril 2014 - 22:25:55

Fichier

article-pelleau-jfpc2013.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00925430, version 1

Citation

Marie Pelleau, Antoine Miné, Charlotte Truchet, Frédéric Benhamou. Un solveur de contraintes basé sur les domaines abstraits. 9èmes Journées Francophones de Programmation par Contraintes, Jun 2013, Aix-en-Provence, France. pp.259-268, 2013. 〈hal-00925430〉

Partager

Métriques

Consultations de la notice

355

Téléchargements de fichiers

338