Skip to main content
Article
A Comparison of Modified Reconstructability Analysis and Ashenhurst‐Curtis Decomposition of Boolean Functions
Kybernetes
  • Anas Al-Rabadi, Portland State University
  • Marek Perkowski, Portland State University
  • Martin Zwick, Portland State University
Document Type
Post-Print
Publication Date
1-1-2004
Subjects
  • Cybernetics,
  • Boolean functions,
  • Computational complexity,
  • Symbolic and mathematical logic
Abstract
Modified reconstructability analysis (MRA), a novel decomposition technique within the framework of set‐theoretic (crisp possibilistic) reconstructability analysis, is applied to three‐variable NPN‐classified Boolean functions. MRA is superior to conventional reconstructability analysis, i.e. it decomposes more NPN functions. MRA is compared to Ashenhurst‐Curtis (AC) decomposition using two different complexity measures: log‐functionality, a measure suitable for machine learning, and the count of the total number of two‐input gates, a measure suitable for circuit design. MRA is superior to AC using the first of these measures, and is comparable to, but different from AC, using the second.
Description

Authors' version of an article which subsequently appeared in Kybernetes, published by Emerald Group Publishing Limited. The version of record may be found at http://dx.doi.org/10.1108/03684920410533985.

DOI
10.1108/03684920410533985
Persistent Identifier
http://archives.pdx.edu/ds/psu/16499
Citation Information
Al-Rabadi, A., Zwick, M., and Perkowski, M. (2004). "A Comparison of Modified Reconstructability Analysis and Ashenhurst-Curtis Decomposition of Boolean Functions." Kybernetes, vol. 33, No. 5/6, pp. 933-947.