Abstract:
We introduce and examine some properties of a new complexity measure for Boolean functions. Unlike classical approaches, which are largely concerned with resource require...Show MoreMetadata
Abstract:
We introduce and examine some properties of a new complexity measure for Boolean functions. Unlike classical approaches, which are largely concerned with resource requirements, the measure examined here aims at quantifying the potential for lazy evaluation in a function. This measure is motivated by issues arising in the implementation of demand-driven logic simulators. The range of values that can be taken by the measure is precisely identified and a lower bound on the complexity of 'almost all' Boolean functions derived. In addition asymptotically exact values are derived for the class of all Boolean symmetric functions.<>
Published in: IEEE Transactions on Computers ( Volume: 44, Issue: 4, April 1995)
DOI: 10.1109/12.376165