JavaScript is disabled for your browser. Some features of this site may not work without it.
Realizing Boolean Functions on Disjoint Sets of Variables

Author
Paul, Wolfgang J.
Abstract
For switching functions $f$ let $C(f)$ be the combinatorial complexity of $f$. We prove that for every $\varepsilon greater than 0$ there are arbitrarily complex functions $f:\{0,1\}^{n} \rightarrow \{0,1\}^{n}$ such that $C(fxf) \leq (1+ \varepsilon) C(f)$ and arbitrarily complex functions $g:\{0,1\}$ such that $C(v c(fxf)) \leq (1 + \varepsilon)C(f)$. These results and the techniques developed to obtain them are used to show, that Ashenhurst decomposition of switching functions does not always yield optimal circuits and to prove a new result concerning the trade-off between circuit size and monotone circuit size.
Date Issued
1975-10Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR75-215
Type
technical report