Flajolet, P.; Prodinger, H. Register allocation for unary-binary trees. (English) Zbl 0612.68065 SIAM J. Comput. 15, 629-640 (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. Cited in 1 ReviewCited in 15 Documents MSC: 68R99 Discrete mathematics in relation to computer science 68N99 Theory of software 68Q25 Analysis of algorithms and problem complexity Keywords:analysis of algorithms; register allocation; random trees; Mellin transform; evaluation of arithmetic expressions; singularity analysis; generating functions; Mellin inversion; unary-binary trees PDFBibTeX XMLCite \textit{P. Flajolet} and \textit{H. Prodinger}, SIAM J. Comput. 15, 629--640 (1986; Zbl 0612.68065) Full Text: DOI