On the Parallel Evaluation of Boolean Expressions
Explore this paper's citation graph
Summary
A bound for the number of steps that are required to evaluate Boolean expressions is obtained and it is shown that any Boolean expression of n distinct variables may be evaluated in two steps if sufficiently many processors are available.
- Type
- article
- Published
- 1976-12-01
- Cited by
- 4
- References
- 0
- OpenAlex
- https://openalex.org/W2003057888
- Semantic Scholar
- https://api.semanticscholar.org/CorpusID:30395403
Keywords
Boolean expression, Boolean function, Maximum satisfiability problem, Product term, Boolean network
References
No references recorded for this paper.
Cited by
- Sequential Evaluation of Boolean Functions
- Reduction of Depth of Boolean Networks with a Fan-In Constraint
- Efficient Parallel Evaluation of Boolean Expressions
- On a Relation Between the Depth and Complexity of Monotone Boolean Formulas
- On a relation between the depth and complexity of monotone Boolean formulas
Related papers
- Boolean Matching for Incompletely Specified Functions
- Boolean Matching for Incompletely Specified Functions
- Boolean Matching Based on Boolean Unification
- Boolean Functions as Models for Quantified Boolean Formulas
- Solving Non-Boolean Satisfiability Problems with the Davis-Putnam Method
- Boolean matching based on Boolean unification
- Cofactor-based NPN boolean matching algorithm