Register Allocation for Unary–Binary Trees
Philippe Flajolet, Helmut Prodinger · SIAM Journal on Computing · 1986
We study the number of registers required for evaluating arithmetic expressions formed with any set of unary and binary operators. Our approach consists in a singularity analysis of intervening generating functions combined with a use of (complex) Mellin inversion. We illustrate it first by rederiving the known results about binary trees and then extend it to the fully general case of unary–binary trees. The method used, as mentioned in the conclusion, is applicable to a wide class of combinatorial sums.