A Complexity Calculus for Recursive Tree Algorithms
Flajolet, Philippe ; Steyaert, Jean-Marc
Publications du Département de mathématiques (Lyon), (1984), p. 39-88 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)
Publié le : 1984-01-01
@article{PDML_1984___6B_A3_0,
     author = {Flajolet, Philippe and Steyaert, Jean-Marc},
     title = {A Complexity Calculus for Recursive Tree Algorithms},
     journal = {Publications du D\'epartement de math\'ematiques (Lyon)},
     year = {1984},
     pages = {39-88},
     mrnumber = {802632},
     zbl = {0537.68040},
     language = {en},
     url = {http://dml.mathdoc.fr/item/PDML_1984___6B_A3_0}
}

Flajolet, Philippe; Steyaert, Jean-Marc. A Complexity Calculus for Recursive Tree Algorithms. Publications du Département de mathématiques (Lyon),  (1984), pp. 39-88. http://gdmltest.u-ga.fr/item/PDML_1984___6B_A3_0/

[BR 82] J. Berstel, C. Reutenauer : "Recognizable formal power series on trees", Theor. Comp. Sc. 18 (1982) pp. 188-145 | MR 652467 | Zbl 0485.68077

[Bu 85] W. Burge : Recursive programming techniques Addison Wesley, Reading (1975) | Zbl 0321.68002

[Da 1878] G. Darboux : "Mémoire sur l'approximation des fonctions de très grands nombres, et sur une classe étendue de développements en série", J. de Mathématiques pures et appliquées, 3ème série, tome VI, (Jan 1878) pp. 1-56 | JFM 10.0279.01

[FO 82] P. Flajolet, A. Odlyzko : "The average height of binary trees and other simple trees", JCSS, vol. 25, No 2, (Oct. 1982) pp. 171-213 | MR 680517 | Zbl 0499.68027

[FS 70] D. Foata, M. P. Schutzenberger : Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics 138, Springer Verlag, Berlin (1970) | MR 272642 | Zbl 0214.26202

[Go 60] I. J. Good : "Generalizations to several variables of Lagrange's expansion, with applications to stochastic processes", Proc. Cambridge Phil. Soc. 56 (1960) pp. 367-380 | MR 123021 | Zbl 0135.18802

[Go 65] I. J. Good : "The generalization of Lagrange's expansion and the enumeration of trees", Proc. Cambridge Philo. Soc. 61 (1965) pp. 499-517 | MR 175812 | Zbl 0142.41204

[He 74] P. Henrici : "Applied and computational complex analysis, 2 vol J. Wiley, New York (1974) | MR 372162 | Zbl 0313.30001

[JG 81] D. Jackson, I. Goulden : Combinatorial Decompositions and Algebraic Enumerations (to appear)

[Kn 68] D. E. Knuth : The art of computer programming : Fundamental Algorithms, Addison Wesley, Reading (1968) | MR 3077152 | Zbl 1127.68068

[Kn 73] D. E. Knuth : The art of computer programming : Sorting and Searching, Addison Wesley, Reading (1973) | MR 378456 | Zbl 0302.68010

[MM 78] A. Meir, J. W. Moon : "On the altitude of nodes in random trees", Canad. J. of Math 30 (1978), pp. 997-1015 | MR 506256 | Zbl 0394.05015

[Od 82] A. Odlyzko : "Periodic oscillations of coefficients of power series that satisfy functional equations" Adv. in Math. 44 (1982), pp. 180-205. | MR 658540 | Zbl 0484.30002

[Po 37] G. Polya : "Kombinatorische Anzahlbestimmungen für Graphen, Grupen und Chemische Verbindungen", Acta Mathematica 68 (1937), pp. 145-254 | MR 1577579 | Zbl 0017.23202

[Ra 79] L. Ramshaw : "Formalizing the analysis of algorithms", Ph. D Thesis, Stanford Univ. (1979)

[Ro 75] G. C. Rota : Finite Operator Calculs, Academic Press, New-York (1975) | MR 379213

[SF 82] J. M. Steyaert, P. Flajolet : "Patterns and Pattern-matching in trees : an analysis", (to appear in Inf. & Control). | MR 750401 | Zbl 0567.68053

[Th 73] J. W. Thatcher : "Tree automata : an informal survey", in Currents in the Theory of Computing (A.V. Aho, ed), Prentice Hall (1973) pp. 143-178. | MR 426502

[Vu 80] J. Vuillemin "A unifying look at data structures", CACM 23 (1980), pp. 229-239. | MR 567151 | Zbl 0434.68047

[We 75] B. Wegbreit : "Mechanical program analysis", CACM 18 (1975), pp. 528-532. | MR 405909 | Zbl 0306.68008

[We 76] B. Wegbreit : "Verifying program performance, JACM 23 (1976), pp. 691-699. | MR 445894 | Zbl 0333.68013