On the Horton-Strahler number for combinatorial tries
Nebel, Markus E.
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000), p. 279-296 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU) 
@article{ITA_2000__34_4_279_0,
     author = {Nebel, Markus E.},
     title = {On the Horton-Strahler number for combinatorial tries},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {34},
     year = {2000},
     pages = {279-296},
     mrnumber = {1809861},
     zbl = {0966.05019},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2000__34_4_279_0}
}

Nebel, Markus E. On the Horton-Strahler number for combinatorial tries. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 34 (2000) pp. 279-296. http://gdmltest.u-ga.fr/item/ITA_2000__34_4_279_0/

[1] M. Abramowitz and I. A. Stegun, Handbook of Mathematical Functions. Dover (1970).

[2] T. M. Apostol, Introduction to Analytic Number Theory. Springer (1976). | MR 434929 | Zbl 0335.10001

[3] N. G. De Bruijn, D. E. Knuth and S. O. Rice, The Average Height of Planted Plane Trees. Graph Theory and Computing, edited by R.C. Read. Academic Press (1972). | MR 505710 | Zbl 0247.05106

[4] L. Devroye and P. Kruszewski, On the Horton-Strahler Number for Random Tries. Theoret. Informatics Appl. 30 (1996) 443-456. | Numdam | MR 1435732 | Zbl 0867.68087

[5] M. Drmota, Asymptotic Distributions and a Multivariate Darboux Method in Enumeration Problems. J. Combin. Theory Ser. A 67 (1994) 169-184. | MR 1284406 | Zbl 0801.60016

[6] A. P. Ershov, On Programming of Arithmetic Operations. Comm. ACM 1 (1958 3-6. | Zbl 0086.33203

[7] P. Flajolet, J. C. Raoult and J. Vuillemin, The Number of Registers required for Evaluating Arithmetic Expressions. Theoret. Comput. Sci. 9 (1979) 99-125. | MR 535127 | Zbl 0407.68057

[8] P. Flajolet and A. Odlyzko, Singularity Analysis of Generating Functions. SIAM J. Discrete Math. 3 (1990) 216-240. | MR 1039294 | Zbl 0712.05004

[9] P. Flajolet and H. Prodinger, Register Allocation for Unary-Binary Trees. SIAM J. Comput. 15 (1986) 629-640. | MR 850413 | Zbl 0612.68065

[10] P. Flajolet, X. Gourdon and P. Dumas, Mellin transforms and asymptotics: Harmonic sums. Theoret Comput. Sci. 144 (1995) 3-58. | MR 1337752 | Zbl 0869.68057

[11] J. Françon, Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique. Theoret. Informatics Appl. 18 (1984) 355-364. | Numdam | MR 775838 | Zbl 0547.68041

[12] R. E. Horton, Erosioned development of systems and their drainage basins, hydrophysical approach to quantitative morphology. Bull. Geol. Soc. of America 56 (1945) 275-370.

[13] R. Kemp, The Average Number of Registers Needed to Evaluate a Binary Tree Optimally. Acta Inform. 11 (1979) 363-372. | MR 533482 | Zbl 0395.68059

[14] R. Kemp, A Note on the Stack Size of Regularly Distributed Binary Trees. BIT 20 (1980) 157-163. | MR 583031 | Zbl 0428.68076

[15] R. Kemp, Fundamentals of the Average Case Analysis of Particular Algorithms. Wiley-Teubner Series in Computer Science (1984). | MR 786659 | Zbl 0638.68026

[16] R. Kemp, On the Stack Ramification of Binary Trees. Random Graphs 2 (1992) 117-138. | MR 1166611 | Zbl 0825.68492

[17] D. E. Knuth, The Art of Computer Programming, Volume 1: Fundamental Algorithms, 3rd Ed. Addison-Wesley (1997). | MR 378456 | Zbl 0895.68055

[18] A. Meir, J. W. Moon and J. R. Pounder, On the Order of Random Channel Networks. SIAM J. Algebraic Discrete Math. 1 (1980) 25-33. | MR 563011 | Zbl 0496.94020

[19] M. E. Nebel, New Results on the Stack Ramification of Binary Trees. J. Autom. Lang. Comb. 2 (1997) 161-175. | MR 1611168 | Zbl 0895.68071

[20] M. E. Nebel, The Stack-Size of Tries, A Combinatorial Study. Theoret. Comput. Sci. (to appear). | MR 1871080 | Zbl 0988.68137

[21] M. E. Nebel, The Stack-Size of Uniform Random Tries Revisited (submitted).

[22] A. N. Strahler, Hypsometric (area-altitude) analysis of erosonal topology. Bull. Geol. Soc. of America 63 (1952) 1117-1142.