The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. ex. Some numerals are expressed as "XNUMX".
Copyrights notice
The original paper is in English. Non-English content has been machine-translated and may contain typographical errors or mistranslations. Copyrights notice
Pour un ensemble arbitraire B de fonctions booléennes satisfaisant une certaine condition, nous donnons une méthode générale de construction d'une classe CB de formules booléennes à lecture unique sur la base B qui a la propriété suivante : Pour tout F in CB, F peut être transformé en une formule optimale (c'est-à-dire une formule la plus simple sur la base standard {AND, OR, NOT}) en remplaçant chaque occurrence d'une fonction de base h ∈ B in F avec une formule optimale pour h. Pour un ensemble particulier de fonctions de base B* = {AND,OR,NOT,XOR,MUX}, nous donnons une représentation sous forme canonique pour CB* de sorte que l'ensemble des formules de forme canonique se compose uniquement de représentants NPN dans CB*.
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
Copier
Hideaki FUKUHARA, Eiji TAKIMOTO, Kazuyuki AMANO, "NPN-Representatives of a Set of Optimal Boolean Formulas" in IEICE TRANSACTIONS on Fundamentals,
vol. E93-A, no. 6, pp. 1008-1015, June 2010, doi: 10.1587/transfun.E93.A.1008.
Abstract: For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/transfun.E93.A.1008/_p
Copier
@ARTICLE{e93-a_6_1008,
author={Hideaki FUKUHARA, Eiji TAKIMOTO, Kazuyuki AMANO, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={NPN-Representatives of a Set of Optimal Boolean Formulas},
year={2010},
volume={E93-A},
number={6},
pages={1008-1015},
abstract={For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.},
keywords={},
doi={10.1587/transfun.E93.A.1008},
ISSN={1745-1337},
month={June},}
Copier
TY - JOUR
TI - NPN-Representatives of a Set of Optimal Boolean Formulas
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1008
EP - 1015
AU - Hideaki FUKUHARA
AU - Eiji TAKIMOTO
AU - Kazuyuki AMANO
PY - 2010
DO - 10.1587/transfun.E93.A.1008
JO - IEICE TRANSACTIONS on Fundamentals
SN - 1745-1337
VL - E93-A
IS - 6
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - June 2010
AB - For an arbitrary set B of Boolean functions satisfying a certain condition, we give a general method of constructing a class CB of read-once Boolean formulas over the basis B that has the following property: For any F in CB, F can be transformed to an optimal formula (i.e., a simplest formula over the standard basis {AND, OR, NOT}) by replacing each occurrence of a basis function h ∈ B in F with an optimal formula for h. For a particular set of basis functions B* = {AND,OR,NOT,XOR,MUX}, we give a canonical form representation for CB* so that the set of canonical form formulas consists of only NPN-representatives in CB*.
ER -