DocumentCode :
761071
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
Volume :
44
Issue :
4
fYear :
1995
fDate :
4/1/1995 12:00:00 AM
Firstpage :
495
Lastpage :
502
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;
fLanguage :
English
Journal_Title :
Computers, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9340
Type :
jour
DOI :
10.1109/12.376165
Filename :
376165
Link To Document :
بازگشت