Sur le nombre de registres nécessaires à l’évaluation d’une expression arithmétique. (French) Zbl 0547.68041

Summary: The distribution of the variable ”number of registers required for evaluating an arithmetic expression” on binary trees is studied in a purely combinatorial way. A new recurrence relation is proved. This relation gets a new proof, without calculations, of the theorem of Flajolet, Raoult and Vuillemin linking this distribution to the distribution of the ”left height” of a binary tree.


68W30 Symbolic computation and algebraic computation
05C05 Trees
11A55 Continued fractions
11B37 Recurrences
68R10 Graph theory (including graph drawing) in computer science
Full Text: EuDML


[1] 1. A. P. ERSHOV, On progamming of arithmetic operations, CACM, vol. 1, n^\circ 8, 1958, p. 3-6. Zbl0086.33203 · Zbl 0086.33203 · doi:10.1145/368892.368907
[2] 2. P. FLAJOLET, Combinatorial aspects of continued fractions, Discrete Math., vol. 32, 1980, p. 125-161. Zbl0445.05014 MR592851 · Zbl 0445.05014 · doi:10.1016/0012-365X(80)90050-3
[3] 3. P. FLAJOLET, Analyses d’algorithmes de manipulation d’arbres et de fichiers, Cahiers du B.U.R.O., p. 34-35, 1981.
[4] 4. P. FLAJOLET et J. FRANÇON, Notes non publiées.
[5] 5. P. FLAJOLET, J. C. RAOULT et J. VUILLEMIN, The number of registers required for evaluating arithmetic expressions, Theor. Comp. Sc, vol. 9, 1979, p. 99-125. Zbl0407.68057 MR535127 · Zbl 0407.68057 · doi:10.1016/0304-3975(79)90009-4
[6] 6. J. FRANÇON, Des codes pour arbres binaires, Actes du 2e Colloque de Lille, Les arbres en algèbre et en programmation, 17-19 février 1977. Zbl0367.94038 · Zbl 0367.94038
[7] 7. J. FRANÇON et G. VIENNOT, Permutations selon leurs pics, creux, doubles montées et doubles descentes, nombres d’Euler et nombres de Genocchi, Discrete Math., vol. 28, 1979, p. 21-35. Zbl0409.05003 MR542933 · Zbl 0409.05003 · doi:10.1016/0012-365X(79)90182-1
[8] 8. R. E. HORTON, Erosional development of streams and their drainage basins: hydrophysical approach to quantitative morphology, Bull. of the Geological Soc. of America, vol. 56 1945, p. 275-370.
[9] 9. R. KEMP, The average number of registers needed to evaluate a binary tree optimally, Acta Informatica, vol. 11 1979, p. 363-372. Zbl0395.68059 MR533482 · Zbl 0395.68059 · doi:10.1007/BF00289094
[10] 10. D. E. KNUTH, The Art of Computer Programming, vol. 1, Addison-Wesley, 1968. Zbl0191.17903 MR378456 · Zbl 0191.17903
[11] 11. O. PERRON, Die Lehre von den Kettenbrüchen, Teubner, Leipzig und Berlin, 1929. JFM55.0262.09
[12] 12. R. SETHI et J. D. ULLMAN, The generation of optimal codefor arithmetic expressions, JACM, vol. 17, 1970, p. 715-728. Zbl0212.18802 MR275722 · Zbl 0212.18802 · doi:10.1145/321607.321620
[13] 13. P. S. STEVENS, Patterns in Nature, Little, Brown and Co., 1974. Traduction française : Les formes dans la nature, Seuil, Paris, 1978.
[14] 14. A. N. STRAHLER, Hypsometric (area-altitude) analysis of erosional topology, Bull. of the Geological Soc. of America, vol. 63 1952, p. 1117-1142.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.