Title :
Efficient Parallel Evaluation of Boolean Expressions
Author :
Preparata, Franco P. ; Muller, David E.
Author_Institution :
Coordinated Science Laboratory and the Department of Electrical Engineering, University of Illinois
fDate :
5/1/1976 12:00:00 AM
Abstract :
A Boolean expression wilth n literals, i.e., n distinct appearances of variables, can be evaluated by a parallel processing system in at most 1.81 log2n steps, or, equivalently, by a network constructed with two-input AND and OR gates and having at most 1.81 log2n levels.
Keywords :
Boolean expressions, combinational networks, computational complexity, evaluation of Boolean expressions, parallel computation.; Arithmetic; Boolean algebra; Computational complexity; Computer networks; Concurrent computing; Context modeling; Contracts; IEL; Mathematics; Propagation delay; Boolean expressions, combinational networks, computational complexity, evaluation of Boolean expressions, parallel computation.;
Journal_Title :
Computers, IEEE Transactions on
DOI :
10.1109/TC.1976.1674647
