Algorithmic Combinatorics on Partial Words
Combinatorics of words (often referred to as Stringology) is an area of combinatorics studying combinatorial and algorithmic properties of sequences of symbols. As such, it has become vital for modern computer science, encompassing and developing (among other topics) data compression and data mining techniques. At the same time, it builds on theoretical grounds of algebraic methods as well as on connections to automata theory. Applications in computer science and bioinformatics need the introduction of probabilistic elements in a similar way to the development of logic (fuzzy logic) and other areas of mathematics oriented to applications. This leads to the notion of partial words, i.e. words with incomplete information in terms of wild cards in the place of some characters.
This book is the first reference book on the theory of partial words. In 12 sections, it gradually leads the reader from a gentle introduction to the topic to an advanced theory. The main goal is to compare combinatorics on partial words to the classical theory of full words. The reader will be surprised at how many of the well-known results from classical semigroup theory can be translated to partial words. The topics treated in various sections start with a discussion of the compatibility relation and equations over partial words, and they further include concepts of periodicity, factorisation, primitivity, codes, solution of special equations and unavoidable sets. Methods range from algebraic methods to algorithms to complexity and present a truly complex treatment of the topic. Every section concludes with exercises sorted by level of difficulty (hints to selected exercise being provided at the end of the book), followed by programming exercises, a bibliography and links to established web interfaces. A complex treatment and presentation makes the book an excellent textbook as well as a reference book for interested researchers in this emerging area on the borderline of algebra, combinatorics and computer science.