Abstract
A description is given of how a tree representing the evaluation of an arithmetic expression can be drawn in such a way that the number of accumulators needed for the computation can be represented in a straightforward manner. This representation reduces the choice of the best order of computation to a specific problem under the theory of graphs. An algorithm to solve this problem is presented.
- 1 NAKATA, I. On compiling algorithms for arithmetic expressions. Comm. ACM 10, 8 (Aug. 1967), 492-494. Google ScholarDigital Library
Index Terms
- On arithmetic expressions and trees
Recommendations
On the number of registers needed to evaluate arithmetic expressions
AbstractThe question of how many temporary storage registers are needed to evaluate compiled arithmetic and masking expressions is discussed. It is assumed that any combination of left-to-right, right-to-left, top-to-bottom, and bottom-to-top techniques ...
Lower bounds on the depth of monotone arithmetic computations
SFCS '92: Proceedings of the 33rd Annual Symposium on Foundations of Computer ScienceConsider an arithmetic expression of length n involving only the operations (+,*) and non-negative constants. The authors prove lower bounds on the depth of any binary computation tree over the same set of operations and constants that computes such an ...
Rainbow domination on trees
This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,...,k} such that for any vertex v with f(...
Comments