Divide-and-conquer References

Introduction

A fundamental idea

Complexity and recurrences

2-rational sequences

Asymptotic behavior

References

1

J.-P. Allouche.
Automates finis en théorie des nombres.
Expositiones Mathematicae, 5:239-266, 1987.

2

J.-P. Allouche and H. Cohen.
Dirichlet series and curious infinite products.
Bulletin of the London Mathematical Society, 17:531-538, 1985.

3

J.-P. Allouche, H. Cohen, M. Mendès France, and J. O. Shallit.
De nouveaux curieux produits infinis.
Acta Arithmetica, XLIX:141-153, 1987.

4

J.-P. Allouche and J. Shallit.
The ring of k-regular sequences.
Theoretical Computer Science, 98:163-197, 1992.

5

T. M. Apostol.
Introduction to Analytic Number Theory.
Springer-Verlag, 1976.

6

A. Arnold and I. Guessarian.
Mathématiques pour l'Informatique.
Logique Mathématiques Informatique. Masson, 2nde edition, 1994.

7

J. Berstel and C. Reutenauer.
Les séries rationnelles et leurs langages.
Masson, Paris, 1984.

8

A. Cobham.
On the base-dependance of sets of numbers recognizable by finite automata.
Mathematical Systems Theory, 3(2):186-192, 1969.

9

Th. Cormen, Ch. Leiserson, and R. Rivest.
Introduction to Algorithms.
MIT Press, New York, 1990.

10

M. Dekking, M. Mendès France, and A. Van der Poorten.
Folds!
Mathematical Intelligencer, 4:130-138, 173-181, 190-195, 1982.

11

H. Delange.
Sur la fonction sommatoire de la fonction somme des chiffres.
L'enseignement Mathématique, XXI(1):31-47, 1975.

12

Ph. Dumas.
Algebraic aspects of B-regular series.
In A. Lingas, R. Karlsson, and S. Carlsson, editors, Automata, Languages and Programming, Lecture Notes in Computer Science, pages 457-468. EATCS, Springer Verlag, 1993.
Proceedings of the 20th International Colloquium, ICALP 93 Lund, Sweden.

13

J.-M. Dumont and A. Thomas.
Systèmes de numération et fonctions fractales relatifs aux substitutions.
Theoretical Computer Science, 65:153-169, 1989.

14

H. Edelsbrunner.
Algorithms in Combinatorial Geometry, volume 10 of EATCS Monographs on Theoretical Computer Science.
Springer-Verlag, 1987.

15

P. Flajolet and G. N. Martin.
Probabilistic counting algorithms for data base applications.
Journal of Computer and System Sciences, 31(2):182-209, October 1985.

16

Ph. Flajolet and M. Golin.
Mellin transforms and asymptotics: The mergesort recurrence.
Acta Informatica, 31:673-696, 1994.

17

Ph. Flajolet, P. Grabner, P. Kirschenhofer, H. Prodinger, and R. Tichy.
Mellin transforms and asymptotics: Digital sums.
Theoretical Computer Science, 123:291-314, 1994.

18

M. L. Fredman and D. E. Knuth.
Recurrence relations based on minimization.
Journal of Mathematical Analysis and Applications, 48:534-559, 1974.

19

Ch. Froidevaux, M.-Cl. Gaudel, and M. Soria.
Types de données et algorithmes.
McGraw-Hill, Paris, 1990.

20

G. H. Gonnet and R. Baeza-Yates.
Handbook of Algorithms and Data Structures: in Pascal and C.
Addison-Wesley, second edition, 1991.

21

D. Greene and D. Knuth.
Mathematics for the Analysis of Algorithms, volume 1 of Progress in Computer Science.
Birkhäuser, 2nd edition, 1982.

22

L. J. Guibas and A. M. Odlyzko.
Periods in strings.
Journal of Combinatorial Theory, Series A, 30:19-42, 1981.

23

L. J. Guibas and A. M. Odlyzko.
Strings overlaps, pattern matching, and nontransitive games.
Journal of Combinatorial Theory, Series A, 30:183-208, 1981.

24

R. Kemp.
Fundamentals of the Average Case Analysis of Particular Algorithms.
Wiley-Teubner, Stuttgart, 1984.

25

D. E. Knuth.
The Art of Computer Programming, volume 3: Sorting and Searching.
Addison-Wesley, 1973.

26

D. E. Knuth.
The Art of Computer Programming, volume 2: Seminumerical Algorithms.
Addison-Wesley, 2nd edition, 1981.

27

D. Kozen.
The Design and Analysis of Algorithms.
Texts and Monographs in Computer Science. Springer-Verlag, 1992.

28

Z. Li and E. M. Reingold.
Solution of a divide-and-conquer maximin recurrence.
SIAM Journal on Computing, 18(6):1188-1200, December 1989.

29

K. Mahler.
On a special functional equation.
Journal of the London Mathematical Society, 15:115-123, 1940.

30

K. Mahler.
Fifty years as a mathematician.
Journal of Number Theory, 14:121-155, 1982.

31

M. Mignotte.
Mathématiques pour le calcul formel.
Presses Universitaires de France, 1989.

32

F. Preparata and M. Shamos.
Computational Geometry, An Introduction.
Springer Verlag, 1985.

33

R. Sedgewick.
Mathematical analysis of combinatorial algorithms.
In G. Louchard and G. Latouche, editors, Probability Theory and Computer Science, chapter 7-12. Academic Press, 1983.

34

R. Sedgewick.
Algorithmes en langage C.
InterEditions, Paris, 1991.

35

K. J. Supowit and E. M. Reingold.
Divide and conquer heuristics for minimum weighted Euclidean matching.
SIAM Journal on Computing, 12(1):118-143, February 1983.

36

G. Tenenbaum.
Introduction à la théorie analytique et probabiliste des nombres.
Institut Elie Cartan, 1992.