Title :
Symmetric and Threshold Boolean Functions Are Exhaustive
Author :
Moret, Bernard M E ; Thomason, Michael G. ; Gonzalez, Rafael C.
Author_Institution :
Department of Computer Science, University of New Mexico
Abstract :
The worst-case number of variable evaluations (testing cost) of Boolean functions is examined. Following up on a result by Rivest and Vuillemin, we show that all symmetric as well as all linearly separable Boolean functions are exhaustive, that is, have a pessimal worst-case testing cost.
Keywords :
Argument complexity; decision tree; multiplexer tree; threshold function; worst-case testing cost; Algorithm design and analysis; Boolean functions; Computer science; Cost function; Decision trees; Logic design; Multiplexing; Pattern analysis; Pattern recognition; Testing; Argument complexity; decision tree; multiplexer tree; threshold function; worst-case testing cost;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1983.1676189
