Algorithmic Combinatorics on Partial Words

Algorithmic Combinatorics on Partial Words is a book in the area of combinatorics on words, and more specifically on partial words. It was written by Francine Blanchet-Sadri, and published in 2008 by Chapman & Hall/CRC in their Discrete Mathematics and its Applications book series.

Topics

A partial word is a string whose characters may either belong to a given alphabet or be a wildcard character. Such a word can represent a set of strings over the alphabet without wildcards, by allowing each wildcard character to be replaced by any single character of the alphabet, independently of the replacements of the other wildcard characters. Two partial words are compatible when they agree on their non-wildcard characters, or equivalently when there is a string that they both match; one partial word $x$ contains another partial word $y$ if they are compatible and the non-wildcard positions of $x$ contain those of $y$; equivalently, the strings matched by $x$ are a subset of those matched by $y$.

The book has 12 chapters, which can be grouped into five larger parts. The first part consists of two introductory chapters defining partial words, compatibility and containment, and related concepts. The second part generalizes to partial words some standard results on repetitions in strings, and the third part studies the problem of characterizing and recognizing primitive partial words, the partial words that have no repetition. Part four concerns codes defined from sets of partial words, in the sense that no two distinct concatenations of partial words from the set can be compatible with each other. A final part includes three chapters on advanced topics including the construction of repetitions of given numbers of copies of partial words that are compatible with each other, enumeration of the possible patterns of repetitions of partial words, and sets of partial words with the property that every infinite string contains a substring matching the set. Each chapter includes a set of exercises, and the end of the book provides hints to some of these exercises.

Audience and reception

Although Algorithmic Combinatorics on Partial Words is primarily aimed at the graduate level, reviewer Miklós Bóna writes that it is for the most part "remarkably easy to read" and suggests that it could also be read by advanced undergraduates. However, Bóna criticizes the book as being too focused on the combinatorics on words as an end in itself, with no discussion of how to translate mathematical structures of other types into partial words so that the methods of this book can be applied to them. Because of this lack of generality and application, he suggests that the audience for the book is likely to consist only of other researchers specializing in this area. Similarly, although Patrice Séébold notes that this area can be motivated by applications to gene comparison, he criticizes the book as being largely a catalog of its author's own research results in partial words, without the broader thematic overview or identification of the fundamental topics and theorems that one would expect of a textbook, and suggests that a textbook that accomplishes these goals is still waiting to be written.

However, reviewer Jan Kratochvíl is more positive, calling this "the first reference book on the theory of partial words", praising its pacing from introductory material to more advanced topics, and writing that it well supports its underlying thesis that many of the main results in the combinatorics of words without wildcards can be extended to partial words. He summarizes it as "an excellent textbook as well as a reference book for interested researchers".