Graphes et couplages en CoqReport as inadecuate




Graphes et couplages en Coq - Download this document for free, or read online. Document in PDF available to download.

1 CEDRIC - Centre d-Etude et De Recherche en Informatique du Cnam

Résumé : Nous proposons une formalisation en Coq des graphes orientés et non orientés et des notions associées. La bibliothèque développée offre non seulement l-expressivité requise pour exprimer et démontrer des propriétés sur les graphes mais aussi une implantation purement fonctionnelle permettant de mettre en oeuvre efficacement les algorithmes de graphe.Nous spécifions ensuite à l-aide de cette bibliothèque les notions de couplage et d-ensemble de sommets couvrant et développons un vérificateur formellement vérifié dont l-objectif est de certifier le résultat d-un fonction qui calcule un couplage maximal. Le code exécutable de ce vérificateur est obtenu grâce au mécanisme d-extraction de Coq. Ce travail est une première contribution d-un projet plus ambitieux qui concerne le développement d-un algorithme de filtrage formellement vérifié pour la contrainte de différence alldiff pour des domaines finis. Ce dernier algorithme utilise de nombreuses manipulations de graphe dont le calcul d-un couplage maximal.





Author: Catherine Dubois - Sourour Elloumi - Benoit Robillard - Clément Vincent -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents