Une nouvelle stratégie de mise sous forme prénexe pour des formules booléennes quantifiées avec bi-implications - Université d'Angers Accéder directement au contenu
Article Dans Une Revue Revue I3 - Information Interaction Intelligence Année : 2009

Une nouvelle stratégie de mise sous forme prénexe pour des formules booléennes quantifiées avec bi-implications

Résumé

La plupart des procédures pour résoudre le problème de validitédes formules booléennes quantifiées prennent en entrée seulement des formules sous forme normale négative, voire sous forme normale conjonctive, et donc prénexes. Mais, il est rarement naturel d’exprimer un problème directement sous cette forme. Par exemple, en spécification, des symboles propositionnels existentiellement quantifiés sont insérés, selon un même motif, pour capturer des résultats intermédiaires. Ainsi, pour pouvoir utiliser les solveurs de l’état de l’art, il est nécessaire de convertir toute formule booléenne quantifiée sous forme prénexe. Un problème majeur de cette mise sous forme prénexe est qu’elle détruit complètement la structure originale de la formule. De plus, lors de la mise sous forme prénexe des bi-implications il y a duplication de leurs sous-formules, ceci incluant les quantificateurs. Cela conduit généralement à une croissance exponentielle de la taille de la formule. Dans ce travail, nous nous focalisons sur le motif très courant des résultats intermédiaires. Nous mettons en évidence des équivalences logiques qui permettent d’extraire les sous-formules améliorant ainsi nettement les performances des solveurs de l’état de l’art.

Fichier principal
Vignette du fichier
i309.pdf (257.87 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)

Dates et versions

hal-03350575 , version 1 (21-09-2021)

Identifiants

  • HAL Id : hal-03350575 , version 1
  • OKINA : ua4259

Citer

Benoit da Mota, Igor Stéphan, Pascal Nicolas. Une nouvelle stratégie de mise sous forme prénexe pour des formules booléennes quantifiées avec bi-implications. Revue I3 - Information Interaction Intelligence, 2009, 9 (2), Non spécifié. ⟨hal-03350575⟩

Collections

UNIV-ANGERS LERIA
3 Consultations
31 Téléchargements

Partager

Gmail Facebook X LinkedIn More