''Algorithmic Combinatorics on Partial Words'' is a book in the area of combinatorics on words, and more specifically on

partial word In computer science and the study of combinatorics on words, a partial word is a string that may contain a number of "do not know" or "do not care" symbols i.e. placeholders in the string where the symbol value is not known or not specified. More ...

s. 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

is a

string String or strings may refer to: *String (structure), a long flexible structure made from threads twisted together, which is used to tie, bind, or hang other objects Arts, entertainment, and media Films * ''Strings'' (1991 film), a Canadian anim ...

whose characters may either belong to a given

alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...

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 Miklós Bóna (born October 6, 1967, in Székesfehérvár) is an American mathematician of Hungarian origin. Bóna completed his undergraduate studies in Budapest and Paris, then obtained his Ph.D. at MIT in 1997 as a student of Richard P. Sta ...

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 Jan Kratochvíl (born 10 February 1959) is a Czech mathematician and computer scientist whose research concerns graph theory and intersection graphs. Kratochvíl was born on 10 February 1959 in Prague. He studied at Charles University in Prague, ...

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".

References

{{reflist, refs= {{citation , last = Bóna , first = Miklós , authorlink = Miklós Bóna , date = September 2009 , doi = 10.1145/1620491.1620497 , issue = 3 , journal =

ACM SIGACT News ACM SIGACT or SIGACT is the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory, whose purpose is support of research in theoretical computer science. It was founded in 1968 by Patrick C. Fischer. Publ ...

, pages = 39–41 , title = Review of ''Algorithmic Combinatorics on Partial Words'' , url = https://www.cs.umd.edu/~gasarch/bookrev/40-3.pdf , volume = 40 {{citation , last = Kratochvíl , first = Jan , author-link = Jan Kratochvíl , contribution = Review of ''Algorithmic Combinatorics on Partial Words'' , contribution-url = https://euro-math-soc.eu/review/algorithmic-combinatorics-partial-words , date = June 2011 , publisher = European Mathematical Society , title = EMS Reviews {{citation , last = Séébold , first = Patrice , work = MathSciNet , mr = 2384993 , title = Review of ''Algorithmic Combinatorics on Partial Words'' , year = 2009 Combinatorics on words Mathematics books 2008 non-fiction books