Une nouvelle sémantique pour la programmation logique capturant la sémantique des modèles stables : la sémantique des extensions

Résumé : La programmation par ensembles r éponses (Answer Set Programming) est un cadre bien étudi é en programmation logique. Plusieurs travaux ont été faits pour d éfinir une s émantique pour les programmes logiques. La plupart de ces s émantiques sont en fait des s émantiques de point fi xe. L'id ée principale est le calcul de mod èles canoniques du programme logique consid ér é, appel és mod èles stables. Les mod èles stables sont dans un certain sens des mod èles minimaux des programmes r éduits. Nous introduisons une nouvelle s emantique pour les programmes logiques, à partir d'une notion d'extension d'une formule propositionnelle classique. Ces extensions peuvent être calcul és de mani ère it érative. Un programme logique est alors cod é par un ensemble de clauses de la logique propositionnelle. On prouve que chaque formule consistante admet au moins une extension et que, pour chaque mod èle stable d'un programme logique, il existe une extension de son codage qui l'implique logiquement. Certaines des extensions ne correspondent pas à un mod èle stable mais sont int eréssantes. Nous donnons une condition discriminante simple qui permet de reconnaitre de telles extensions. En fin, nous d écrivons un algorithme qui calcule les extensions de la formule CNF codant le programme logique. De cet ensemble d'extension on peut extraire les mod èles stables du programme logique initial.
Type de document :
Communication dans un congrès
Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

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

https://hal.inria.fr/hal-00829608
Contributeur : Ist Inria Saclay <>
Soumis le : lundi 3 juin 2013 - 15:26:10
Dernière modification le : jeudi 18 janvier 2018 - 02:20:33
Document(s) archivé(s) le : mercredi 4 septembre 2013 - 04:13:54

Fichier

paper_31.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00829608, version 1

Collections

Citation

Belaïd Benhamou, Pierre Siegel. Une nouvelle sémantique pour la programmation logique capturant la sémantique des modèles stables : la sémantique des extensions. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00829608〉

Partager

Métriques

Consultations de la notice

636

Téléchargements de fichiers

184