Sur l'efficacité des systèmes de formes normales de fonctions Booléennes

Miguel Couceiro 1 Pierre Mercuriali 2 Romain Péchoux 2
1 ORPAILLEUR - Knowledge representation, reasonning
Inria Nancy - Grand Est, LORIA - NLPKD - Department of Natural Language Processing & Knowledge Discovery
2 CARTE - Theoretical adverse computations, and safety
Inria Nancy - Grand Est, LORIA - FM - Department of Formal Methods
Résumé : Dans cet article, nous comparons différentes représen-tations des fonctions Booléennes à l'aide de systèmes de formes normales. Nous étendons les travaux de [3] sur l'étude asymptotique de l'efficacité des représentations produites par des systèmes de formes normales (Normal Form Systems–NFSs). Nous identifions certaines proprié-tés, comme l'associativité, la linéarité, la quasi-linéarité et la symétrie, qui nous permettent de comparer l'effica-cité des NFSs correspondantes. Nous illustrons ces résul-tats en comparant des NFSs usuelles telles que la DNF, CNF, les représentations polynomiales, ainsi que la forme normale médiane (MNF) et celle dite de Sheffer (SNF). Nous obtenons en particulier que les NFSs générés par un seul connecteur sont polynomialement aussi efficace que ceux générés par plusieurs. La MNF, quand à elle, est aussi efficace que n'importe quel autre système.
Type de document :
Communication dans un congrès
LFA 2017 - 26èmes Rencontres Francophones sur la Logique Floue et ses Applications, Oct 2017, Amiens, France. pp.1-8
Liste complète des métadonnées

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

https://hal.inria.fr/hal-01656033
Contributeur : Pierre Mercuriali <>
Soumis le : mardi 5 décembre 2017 - 13:56:23
Dernière modification le : jeudi 11 janvier 2018 - 06:25:24

Fichier

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

Identifiants

  • HAL Id : hal-01656033, version 1

Citation

Miguel Couceiro, Pierre Mercuriali, Romain Péchoux. Sur l'efficacité des systèmes de formes normales de fonctions Booléennes. LFA 2017 - 26èmes Rencontres Francophones sur la Logique Floue et ses Applications, Oct 2017, Amiens, France. pp.1-8. 〈hal-01656033〉

Partager

Métriques

Consultations de la notice

96

Téléchargements de fichiers

19