Efficient Parallel Evaluation of Boolean Expressions
- 1 May 1976
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers
- Vol. C-25 (5) , 548-549
- https://doi.org/10.1109/TC.1976.1674647
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
This publication has 1 reference indexed in Scilit:
- The Parallel Evaluation of Arithmetic Expressions Without DivisionIEEE Transactions on Computers, 1973