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
Abstract : In this paper we compare various normal form representations of Boolean functions. We extend the study of [3] pertaining to the comparison of the asymptotic efficiency of representations produced by normal form systems (NFSs). We identify some properties, such as as-sociativity, linearity, quasi-linearity and symmetry, that allow the efficiency of the corresponding NFSs to be compared. We illustrate these results by comparing well-known NFSs such as the DNF, CNF, polynomial (PNF) representations, as well as the Median Normal Form (MNF) and Sheffer Normal Form (SNF). We obtain in particular that NFSs generated by a single connective are polynomially as efficient as those generated by several connectives. As for the MNF, it is as efficient as any other NFS.
Document type :
Conference papers
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01656033
Contributor : Pierre Mercuriali <>
Submitted on : Tuesday, December 5, 2017 - 1:56:23 PM
Last modification on : Tuesday, December 18, 2018 - 4:48:02 PM

File

LFA_2017_paper_7.pdf
Files produced by the author(s)

Identifiers

  • 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⟩

Share

Metrics

Record views

293

Files downloads

62