×

Register allocation for unary-binary trees. (English) Zbl 0612.68065

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.

MSC:

68R99 Discrete mathematics in relation to computer science
68N99 Theory of software
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI