Sur l'efficacité des systèmes de formes normales de fonctions Booléennes
| Autor: | Miguel Couceiro, Pierre Mercuriali, Romain Péchoux |
|---|---|
| Přispěvatelé: | Knowledge representation, reasonning (ORPAILLEUR), Inria Nancy - Grand Est, Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Natural Language Processing & Knowledge Discovery (LORIA - NLPKD), Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Institut National de Recherche en Informatique et en Automatique (Inria)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL), Theoretical adverse computations, and safety (CARTE), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Department of Formal Methods (LORIA - FM), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Laboratoire Lorrain de Recherche en Informatique et ses Applications (LORIA), Institut National de Recherche en Informatique et en Automatique (Inria)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS)-Université de Lorraine (UL)-Centre National de la Recherche Scientifique (CNRS) |
| Jazyk: | francouzština |
| Rok vydání: | 2017 |
| Předmět: | |
| Zdroj: | LFA 2017-26èmes Rencontres Francophones sur la Logique Floue et ses Applications LFA 2017-26èmes Rencontres Francophones sur la Logique Floue et ses Applications, Oct 2017, Amiens, France. pp.1-8 HAL |
| Popis: | National audience; 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.; 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|