| HAL-Inria | Publications, software ... of Inria's scientists |
Conference papers
Normal form systems generated by single connectives have mutually equivalent efficiency
Abstract : In this paper we consider a Normal Form System (NFS) as being a factorization of the class of all Boolean functions into a composition of clones. This formalism includes classical normal forms such as DNF, CNF,. .. We study the efficiency of NFSs that yield terms built using one or several connectives taken in a fixed order, and applied to literals and constants. Here, efficiency is measured by the minimal size of terms representing a function. Each clone is finitely generated but can have different sets of generators. We show that the choice of the generator used in a given NFS does not impact its efficiency, up to polynomial equivalence.
Cited literature [9 references]
https://hal.inria.fr/hal-02499377
Contributor : Romain Péchoux <>
Submitted on : Thursday, March 5, 2020 - 11:07:12 AM
Last modification on : Thursday, March 5, 2020 - 7:01:05 PM
Document(s) archivé(s) le : Saturday, June 6, 2020 - 1:35:02 PM
Contributor : Romain Péchoux <>
Submitted on : Thursday, March 5, 2020 - 11:07:12 AM
Last modification on : Thursday, March 5, 2020 - 7:01:05 PM
Document(s) archivé(s) le : Saturday, June 6, 2020 - 1:35:02 PM
File
DICE_2018_paper_7.pdf
Files produced by the author(s)