Analyse d'algorithmes de manipulation d'arbres et de fichiers

 Access to full text

 Full (PDF)

1. [ Batcher ; 1968] : "Sorting networks and their applications" ; in Proceedings AFIPS Spring Joint Comp. Conf., Montvale (1968), pp. 307-314. 
2. [ Bentley ; 1978] : "Decomposable Searching Problems" ; Carnegie-Mellon University Report Nu CMU-CS-78-145 (1978). Zbl0404.68067MR691496
3. [ Berstel ; 1978] : "Séries formelles en variables non-commutatives et applications" ; J. Berstel Editeur, LITP et ENSTA, Paris (1978). Zbl0401.16001MR522632
4. [ de Bruijn ; 1975] Communication personnelle à J. Vuillemin. 
5. [ de Bruijn, Knuth, Rice ; 1972] : "The average height of planted plane trees" ; in "Graph Theory and Computing" ; R.C. Read Editor, Academic Press, New-York (1972), pp. 15-22. Zbl0247.05106MR505710
6. [ Camion, Flajolet, Monier ; 1979] : "On Pollard's factorization algorithm", en préparation. 
7. [ Carlitz ; 1964] : "A binomial identity arising from a sorting problem" ; in SIAM Rev.6 (1964), pp. 20-30. Zbl0128.01601MR167435
8. [ Carlitz ; 1974] : "q-analog of the Lagrange expansion" ; in Eulerian Series and Applications, Pennsylvania State Univ. (1974). 
9. [ Chihara ; 1978] : "An Introduction to Orthogonal Polynomials", Gordon and Breach, New-York (1978). Zbl0389.33008MR481884
10. [ Chomsky, Schützenberger ; 1963] : "The algebraic theory of context-free languages" in "Computer Programming and Formal Systems" ; North Holland P.C. (1963). Zbl0148.00804MR152391
11. [ Chung, Luccio, Wong ; 1979] : "On the complexity of sorting in magnetic bubble memory systems", manuscript. Zbl0436.68041
12. [ Comtet ; 1970] : "Analyse Combinatoire" ; 2 vol. P.U.F., Paris (1970). 
13. [ Delange ; 1975] : "Sur la fonction sommatoire de la fonction somme des chiffres" ; in Enseignement Math.21 (1975), pp. 31-47. Zbl0306.10005MR379414
14. [ Edwards ; 1974] : "Riemann's Zeta Functions" ; Academic Press, New-York (1974). Zbl0315.10035
15. [ Eilenberg ; 1974] : "Automata, Languages and Machines" ; Vol A ; Academic Press, New-York (1974). Zbl0317.94045MR530382
16. [ Ershov ; 1958] : "On programming of arithmetic operations", CACM1 (1958), 8 pp. 3-6. Zbl0086.33203
17. [ Flajolet ; 1978] : "Analyse d'Algorithmes de manipulation de fichiers" ; Rapport IRIA, Rocquencourt (1978). 
18. [ Flajolet ; 1978] : "Analyse de la détection d'arbres" in "3ème Colloque de Lille sur les Arbres en Algèbres et en Programmation" ; Lille (1979). Zbl0399.05024
19. [ Flajolet ; 1979] : "Combinatorial Aspects of Continued Fractions", soumis à Discrete Math. Zbl0445.05014
20. [ Flajolet, Françon, Vuillemin ; 1979a] : "Computing Integrated costs of sequences of operations with application to dictionaries" ; in 11th ACM-SIGACT Conf., Atlanta (1979). MR564619
21. [ Flajolet, Françon, Vuillemin ; 1979b] : "Towards analyzing sequences of operations for dynamic data structures" ; in 20th IEEE-FOCS Conf., Porto-Rico (1979). 
22. [ Flajolet, Ramshaw ; 1979] : "A note on Gray-Code and Odd-Even Merge" ; SIAM Journal on Comp. (à paraître). Zbl0447.68083
23. [ Flajolet, Raoult, Vuillemin ; 1977] : "The number of registers required for evaluating arithmetic expressions" ; version préliminaire dans "18th IEEE Symp. FOCS" (1977) Zbl0407.68057
24. [ Flajolet, Raoult, Vuillemin ; 1979] : "The number of registers required for evaluating arithmetic expressions" ; version préliminaire dans Theoret. Comp. Sc.9 (1979), pp. 99-125. Zbl0407.68057MR535127
25. [ Flajolet, Steyaert ; 1979] : "On the analysis of tree matching algorithms", en préparation. Zbl0434.68046
26. [ Foata ; 1971] : "La série génératrice exponentielle dans les problèmes d'énumération" ; Presses de l'Université de Montréal (1971). Zbl0325.05007
27. [ Foata, Schützenberger ; 1970] : "Théorie géométrique des polynômes Eulériens" ; Lecture Notes in Mathematics, N° 138, Springer Verlag, Berlin (1970). Zbl0214.26202
28. [ Françon ; 1977] : "Sur la fonction nombre de registres", manuscript. 
29. [ Françon ; 1978] : "Histoires de Fichiers" ; in RAIRO Inf. Th., vol. 12 (1978), pp. 49-67. Zbl0377.68034MR483819
30. [ Françon ; 1979] : "Combinatoire des Structures de données" ; Thèse, Faculté des Sciences de Strasbourg (1979). 
31. [ Françon, Viennot ; 1979] : "Permutations selon leurs pics, creux, doubles montées et doubles descentes ; nombres d'Euler et de Genocchi" ; in Discrete Math. (1979), à paraître. Zbl0409.05003
32. [ Françon, Viennot, Vuillemin ; 1978] : "Description and analysis of an efficient priority queue representation" ; in "19th I.E.E.E.F.O.C.S.", Ann Harbor (1978). 
33. [ Françon, Viennot, Vuillemin ; 1978] : "Description et analyse d'une représentation performante des files de priorité" ; Rapport Informatique Université Paris-Sud (1978). 
34. [ Henrici ; 1978] : "Applied and Computation Complex Analysis", vol.2 ; J. Wiley, New-York (1978). 
35. [ Jackson ; 1978] : "Some results on product-weighted lead-codes" ; in J. Comb. Th., ser. A, 25 (1978), pp. 181-187. Zbl0425.05007MR509443
36. [ Kemp ; 1977] : "The average number of registers to evaluate a binary tree optimally", Saarbrücken University Report (1977). 
37. [ Kemp : "The average number of registers to evaluate a binary tree optimally", Acta Informatica (1979). Zbl0395.68059
38. [ Knuth ; 1968] : "The Art of Computer Programming : Fundamental Algorithms" ; Addison Wesley, Reading (1968). Zbl0895.68055
39. [ Knuth ; 1969] : "The Art of Computer Programming : Semi numerical Algorithms" ; Addison-Wesley, Reading (1969). Zbl0191.18001
40. [ Knuth ; 1973] : "The Art of Computer Programming : Sorting and Searching" ; Addison-Wesley, Reading (1973). Zbl0895.68054
41. [ Knuth, Schönhage ; 1978] : "The expected linearity of a simple equivalence algorithm" ; in Stanford Univ. Report CS-77-599 (1977). Zbl0377.68024
42. [ Kreweras ; 1970] : "Sur les éventails de segments" ; Cahiers du B.U.R.O., n° 15 (1970), pp. 1-41. 
43. [ Lucas ; 1891] : "Théorie des Nombres" ; Gauthier-Villard, Paris (1891). 
44. [ Mac Ilroy ; 1974] : "The number of ones in binary integers : bounds and extremal properties" ; in SIAM J. on Comp.3, n°4 (1974), pp. 255-261. Zbl0292.68021MR436687
45. [ Mc Mahon ; 1975] : "The mechanical desing of trees" ; in Scient. Am.233 (1975), 1 pp. 92-102. 
46. [ Meixner ; 1934] : "Orthogonale Polynomsystème mit einem besonderen Gestalt der erzeugenden funktion" ; J. Lond. Math. Soc.9 (1934), pp. 6-13. Zbl0008.16205
47. [ Odlyzko ; 1979] : "Periodic oscillations of coefficients of power series that satisfy functional equations" ; Bell Lab., Murray Hill (1979). Zbl0484.30002
48. [ Perron ; 1954] : "Die Lehre von den Kettenbrüchen", 2 vol. Teubner, Stuttgart (1954). JFM43.0283.04
49. [ Pollard ; 1975] : "A Monte-Carlo method for factorization" ; in BIT. 15 (1975), pp. 331-334. Zbl0312.10006MR392798
50. [ Raney ; 1960] : "Functional composition patterns and power series reversion" ; Trans. A.M.S.94 (1960), pp. 441-451. Zbl0131.01402MR114765
51. [ Read ; 1979] : "The chord intersection problem" ; in Annals of N.Y. Ac. of Sc., 319 (1979), pp. 444-454. Zbl0479.05005MR556055
52. [ Riordan ; 1968] : "Combinatorial Identities", John-Wiley and Sons, New-York (1968), Zbl0194.00502MR231725
53. [ Rogers ; 1907] : "On the representation of certain asymptotic series as continued fractions" ; Proc. Lond. Math. Soc, 2 (1907), pp. 72-89. MR1576106JFM37.0255.02
54. [ Rota ; 1975] : "Finite Operator Calculus" ; Academic Press, New-York (1975). MR379213
55. [ Salomaa, Soittola ; 1978] : "Automata-theoretic Aspects of Formal Power Series" ; Springer Verlag, New-York (1978). Zbl0377.68039MR483721
56. [ Sedgwick ; 1978] : "Data Movement in Odd-Even Merge ; SlAM Journal on Comp.7 (1978), pp. 239-272. Zbl0379.68024MR483680
57. [ Sethi, Ullman ; 1970] : "The generation of optimal code for arithmetic expressions" ; in JACM17 (1970), 4 pp. 715-728, Zbl0212.18802MR275722
58. [ Shreve ; 1966] : "Statistical law of stream numbers" ; in Geology, 74 (1966), pp. 17-37. 
59. [ Stieltjes ; 1889] : "Sur la réduction en fraction continue d'une série procédant suivant les puissances descendantes d'une variable" ; Ann. Fac. Sc. Toulouse, 3 (1889), pp. 1-17. JFM21.0187.01
60. [ Szegö ; 1939] : "Orthogonal Polynomials" ; A.M.S.Colloq. Pub., Providence (1939). 
61. [ Touchard ; 1952] : "Sur un problème de configurations et sur les fractions continues" ; Can. J. of Math.4 (1952), pp. 2-25. Zbl0047.01801MR46325
62. [ Viennot ; 1978] : "Une interprétation combinatoire des développements en série entière des fonctions elliptiques de Jacobi" ; soumis à Discrete Math. (1979). Zbl0444.33002
63. [ Vuillemin ; 1978] : "A Data Structure for Manipulating Priority Queues" ; in CACM, 21 (1978), pp. 309-315. Zbl0371.68011MR478740
64. [ Wall ; 1967] : "Analytic Theory of Continued Fractions" ; Chelsea Pub. Co., New-York (1967) rééd. Zbl0035.03601
65. [ Whittaker, Watson ; 1902] : "A Course on Modern Analysis" ; Cambridge Univ. Press (1902) Zbl45.0433.02JFM45.0433.02
66. [ Widder ; 1971] : "An Introduction to Transform Theory" ; Academic Press, New-York (1971). Zbl0219.44001

1. Jean Françon, Sur le nombre de registres nécessaires à l'évaluation d'une expression arithmétique
2. G. Louchard, The brownian motion : a neglected tool for the complexity analysis of sorted tables manipulation
3. Philippe Flajolet, Thomas Ottmann, Derick Wood, Search trees and bubble memories
4. Dominique Geniet, René Schott, Loÿs Thimonier, A Markovian concurrency measure