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