Applied combinatorics on words. A collective work by Jean Berstel, Dominique Perrin, Maxime Crochemore, Eric Laporte, Mehryar Mohri, Nadia Pisanti, Marie-France Sagot, Gesine Reinert, Sophie Schbath, Michael Waterman, Philippe Jacquet, Wojciech Szpankowski, Dominique Poulalhon, Gilles Schaeffer, Roman Kolpakov, Gregory Koucherov, Jean-Paul Allouche and Valérie Berthé. With a preface by Berstel and Perrin. (English) Zbl 1133.68067

Encyclopedia of Mathematics and Its Applications 105. Cambridge: Cambridge University Press (ISBN 0-521-84802-4/hbk). xv, 610 p. (2005).
This book, coming after “Lothaire 1” and “Lothaire 2” (see Zbl 0874.20040 or Zbl 0514.20045 and Zbl 1001.68093) is devoted to applications of combinatorics on words. The ten chapters, written by 18 authors and unified in style, notations and contents, go from algorithms on words for manipulating vectors to biology. More precisely:
Chapter 1 deals with algorithms on words (from elementary algorithms to tries and automata, from pattern matching to transducers, from parsing to word enumeration, probability distributions and statistics on words.
Chapter 2 is devoted to structures in indexes (from suffice tries to contexts of factors, from suffice automata to indexes, from regularities to pattern matching machines).
Chapters 3 and 4 address the processing of natural languages (symbolic processing and statistical processing including the question of speech recognition).
Chapter 5 is about the inference of network expressions (network expressions are regular expressions without Kleene closure on the alphabet of the input words).
Chapter 6 deals with probabilistic models for biological sequences (applications to biology go from statistical significance of word frequencies in DNA to DNA matching with algorithms like BLAST; several results and tools are carefully studied, including hidden Markov models).
Chapter 7 studies the analytic approach to pattern matching (including a new matching problem called the subsequence pattern matching or the hidden pattern matching).
Chapters 8 and 9 and 10 are, respectively, devoted to periodic structures in words, to counting coding and sampling with words, and to words in number theory.
Each chapter is followed by problems and by historical notes. The book ends with a bibliography of 460 items.
This book is definitely necessary, and it completes nicely Lothaire 1 and Lothaire 2.


68R15 Combinatorics on words
68-02 Research exposition (monographs, survey articles) pertaining to computer science
11B85 Automata sequences
68P05 Data structures
68Q45 Formal languages and automata
68T50 Natural language processing
68W05 Nonnumerical algorithms
92D20 Protein sequences, DNA sequences