Title :
On the complexity of Boolean functions computed by lazy oracles
Author :
Dunne, Paul E. ; Leng, Paul H. ; Nwana, Gerald F.
Author_Institution :
Dept. of Comput. Sci., Liverpool Univ., UK
fDate :
4/1/1995 12:00:00 AM
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
Keywords :
Boolean functions; circuit analysis computing; computational complexity; digital simulation; logic CAD; logic testing; Boolean function complexity; Boolean symmetric functions; asymptotically exact values; complexity measure; demand-driven logic simulators; lazy evaluation; lazy oracles; Boolean functions; Circuit simulation; Circuit synthesis; Digital systems; Discrete event simulation; Formal verification; Logic circuits; Logic design; Logic functions; Logic gates;
Journal_Title :
Computers, IEEE Transactions on