Register Allocation for Unary–Binary Trees

Abstract

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 unaj-binary trees. The method used, as mentioned in the conclusion, is applicable to a wide class of combinatorial sums.