A Complexity Calculus for Recursive Tree Algorithms

Philippe Flajolet; Jean-Marc Steyaert

Publications du Département de mathématiques (Lyon) (1984)

  • Volume: 6/B, Issue: 6B, page 39-88
  • ISSN: 0076-1656

How to cite

top

Flajolet, Philippe, and Steyaert, Jean-Marc. "A Complexity Calculus for Recursive Tree Algorithms." Publications du Département de mathématiques (Lyon) 6/B.6B (1984): 39-88. <http://eudml.org/doc/273362>.

@article{Flajolet1984,
author = {Flajolet, Philippe, Steyaert, Jean-Marc},
journal = {Publications du Département de mathématiques (Lyon)},
keywords = {average case analysis of tree algorithms; algebraic translation rules for data and control structures; restricted programming language over tree structures; generating functions; asymptotic behavior; structurally complex programs; symbolic differentiation algorithms; tree-matching; reduction and simplification of expressions; partial unification},
language = {eng},
number = {6B},
pages = {39-88},
publisher = {Université Claude Bernard - Lyon 1},
title = {A Complexity Calculus for Recursive Tree Algorithms},
url = {http://eudml.org/doc/273362},
volume = {6/B},
year = {1984},
}

TY - JOUR
AU - Flajolet, Philippe
AU - Steyaert, Jean-Marc
TI - A Complexity Calculus for Recursive Tree Algorithms
JO - Publications du Département de mathématiques (Lyon)
PY - 1984
PB - Université Claude Bernard - Lyon 1
VL - 6/B
IS - 6B
SP - 39
EP - 88
LA - eng
KW - average case analysis of tree algorithms; algebraic translation rules for data and control structures; restricted programming language over tree structures; generating functions; asymptotic behavior; structurally complex programs; symbolic differentiation algorithms; tree-matching; reduction and simplification of expressions; partial unification
UR - http://eudml.org/doc/273362
ER -

References

top
  1. [BR 82] J. Berstel, C. Reutenauer : "Recognizable formal power series on trees", Theor. Comp. Sc.18 (1982) pp. 188-145 Zbl0485.68077MR652467
  2. [Bu 85] W. Burge : Recursive programming techniquesAddison Wesley, Reading (1975) Zbl0321.68002
  3. [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 JFM10.0279.01
  4. [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 Zbl0499.68027MR680517
  5. [FS 70] D. Foata, M. P. Schutzenberger : Théorie géométrique des polynômes eulériens, Lecture Notes in Mathematics138, Springer Verlag, Berlin (1970) Zbl0214.26202MR272642
  6. [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 Zbl0135.18802MR123021
  7. [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 Zbl0142.41204MR175812
  8. [He 74] P. Henrici : "Applied and computational complex analysis, 2 vol J. Wiley, New York (1974) Zbl0313.30001MR372162
  9. [JG 81] D. Jackson, I. Goulden : Combinatorial Decompositions and Algebraic Enumerations (to appear) 
  10. [Kn 68] D. E. Knuth : The art of computer programming : Fundamental Algorithms, Addison Wesley, Reading (1968) Zbl1127.68068MR3077152
  11. [Kn 73] D. E. Knuth : The art of computer programming : Sorting and Searching, Addison Wesley, Reading (1973) Zbl0302.68010MR378456
  12. [MM 78] A. Meir, J. W. Moon : "On the altitude of nodes in random trees", Canad. J. of Math30 (1978), pp. 997-1015 Zbl0394.05015MR506256
  13. [Od 82] A. Odlyzko : "Periodic oscillations of coefficients of power series that satisfy functional equations" Adv. in Math.44 (1982), pp. 180-205. Zbl0484.30002MR658540
  14. [Po 37] G. Polya : "Kombinatorische Anzahlbestimmungen für Graphen, Grupen und Chemische Verbindungen", Acta Mathematica68 (1937), pp. 145-254 Zbl0017.23202MR1577579
  15. [Ra 79] L. Ramshaw : "Formalizing the analysis of algorithms", Ph. D Thesis, Stanford Univ. (1979) 
  16. [Ro 75] G. C. Rota : Finite Operator Calculs, Academic Press, New-York (1975) MR379213
  17. [SF 82] J. M. Steyaert, P. Flajolet : "Patterns and Pattern-matching in trees : an analysis", (to appear in Inf. & Control). Zbl0567.68053MR750401
  18. [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. MR426502
  19. [Vu 80] J. Vuillemin "A unifying look at data structures", CACM23 (1980), pp. 229-239. Zbl0434.68047MR567151
  20. [We 75] B. Wegbreit : "Mechanical program analysis", CACM18 (1975), pp. 528-532. Zbl0306.68008MR405909
  21. [We 76] B. Wegbreit : "Verifying program performance, JACM23 (1976), pp. 691-699. Zbl0333.68013MR445894

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.