zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
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. £ 70.00; $ 125.00 (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.

68R15Combinatorics on words
68-02Research monographs (computer science)
11B85Automata sequences
68P05Data structures
68Q45Formal languages and automata
68T50Natural language processing
68W05Nonnumerical algorithms
92D20Protein sequences, DNA sequences