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


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