Comparison of Enhanced Reconstructability Analysis and
Ashenhurst-Curtis Decomposition of Boolean
Functions
Anas Al-Rabadi, Martin Zwick, and Marek
Perkowski
Presented at the 2002
meeting of the World Organization of Systems
and
Cybernetics and the International Institute of General Systems
Studies
Abstract
Modified
Reconstructibility Analysis (MRA), a novel decomposition within the framework of
set-theoretic (crisp possibilistic) Reconstructibility Analysis, is presented.
It is shown that in some cases while 3-variable NPN-classified Boolean functions
are not decomposable using Conventional Reconstructibility Analysis
(CRA), they are decomposable using Modified Reconstructibility Analysis (MRA).
Also, it is shown that whenever a decomposition of 3-variable NPN-classified
Boolean functions exists in both MRA and CRA, MRA yields simpler or equal
complexity decompositions. A comparison of the corresponding complexities for
Ashenhurst-Curtis (AC) decomposition and Modified Reconstructibility Analysis
(MRA) is also presented. While both AC and MRA decompose some but not all
NPN-cases, MRA decomposes more classes, and consequently more Boolean functions.
Discrete Multivariate Modeling
Page