Simplification of Boolean Affine Formulas

Paul Feautrier 1
1 COMPSYS - Compilation and embedded computing systems
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Résumé : Les expressions affines booléennes, qui combinent des inégalités affines à l'aide d'opérateurs booléens, apparaissent dans de nombreux domaines de l'informatique comme l'analyse statique, la génération de code, la synthèse matérielle et le \emph{model checking} symbolique. Elles permettent de représenter de façon compacte des ensembles trés grands et même infinis. Les algorithmes qui permettent de les manipuler ont tendence à construire des formules fortement redondantes et de taille croissante; il est donc nécessaire d'utiliser un simplifieur si l'on veut en maintenir la complexité dans des limites raisonables. La simplification est un problème difficile, au moins aussi difficile que le test de satisfiabilité, et donc de complexité exponentielle dans le pire cas. Cet article propose une nouvelle méthode de simplification, basée sur l'analyse des chemins dans un diagramme de décision ordonné. Cette méthode est capable d'exploiter les régularités d'une formule pour en accélérer la simplification. L'algorithme a été implémenté en Java et testé sur une série d'exemples en provenance de divers domaines d'application.
Type de document :
Rapport
[Research Report] RR-7689, INRIA. 2011, pp.15
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00609519
Contributeur : Paul Feautrier <>
Soumis le : mardi 19 juillet 2011 - 13:07:56
Dernière modification le : mardi 16 janvier 2018 - 15:42:37
Document(s) archivé(s) le : lundi 12 novembre 2012 - 11:15:43

Fichier

RR-7689.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00609519, version 1

Collections

Citation

Paul Feautrier. Simplification of Boolean Affine Formulas. [Research Report] RR-7689, INRIA. 2011, pp.15. 〈inria-00609519〉

Partager

Métriques

Consultations de la notice

271

Téléchargements de fichiers

215