Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1133.68067
Lothaire, M.
(Berstel, Jean; Perrin, Dominique; Crochemore, Maxime; Laporte, Eric; Mohri, Mehryar; Pisanti, Nadia; Sagot, Marie-France; Reinert, Gesine; Schbath, Sophie; Waterman, Michael; Jacquet, Philippe; Szpankowski, Wojciech; Poulalhon, Dominique; Schaeffer, Gilles; Kolpakov, Roman; Koucherov, Gregory; Allouche, Jean-Paul; Berthé, Valérie)
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)
[B] Encyclopedia of Mathematics and Its Applications 105. Cambridge: Cambridge University Press. xv, 610~p. \sterling~70.00; \$~125.00 (2005). ISBN 0-521-84802-4/hbk

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:\par 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.\par 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).\par Chapters 3 and 4 address the processing of natural languages (symbolic processing and statistical processing including the question of speech recognition).\par Chapter 5 is about the inference of network expressions (network expressions are regular expressions without Kleene closure on the alphabet of the input words).\par 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).\par Chapter 7 studies the analytic approach to pattern matching (including a new matching problem called the subsequence pattern matching or the hidden pattern matching).\par 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.\par Each chapter is followed by problems and by historical notes. The book ends with a bibliography of 460 items. \par This book is definitely necessary, and it completes nicely Lothaire 1 and Lothaire 2.
[Jean-Paul Allouche (Orsay)]

MSC 2000:: *68R15 Combinatorics on words
68-02 Research monographs (computer science)
11B85 Automata sequences
68P05 Data structures
68Q45 Formal languages
68T50 Natural language processing
68W05 Nonnumerical algorithms
92D20 Protein sequences, DNA sequences

Keywords: words; algorithms on words; tries; automata; natural languages; biomathematics; DNA sequences; pattern matching; Markov models; number theory

Citations: Zbl 0874.20040; Zbl 0514.20045; Zbl 1001.68093

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]