Parallel Restructuring and Evaluation of Expressions
D. E. Muller, F. P. Preparata · 1988
TERMS (Continuo on r o v in o if necessary e n d identify tty block number) evaluation of expressions, semiring computations, restructuring of expressions, computational complexity, parallel computation, minimum depth networksIn this paper we describe a boolean network of size 0(N logN) which accepts a fully parenthesized N-variable expression over a given semiring and produces its value in O(logN) time.The network consists of two components!, a preprocessor and a universal evaluator.The preprocessor computes the destinations of the expression terms and routes them to the correct input terminals of the universal evaluator.