The discrete mathematics and theoretical computer science communities have recently witnessed explosive growth in the area of algorithmic combinatorics on words. The next generation of research on combinatorics of partial words promises to have a substantial impact on molecular biology, nanotechnology, data communication, and DNA computing. Delving into this emerging research area, Algorithmic Combinatorics on Partial Words presents a mathematical treatment of combinatorics on partial words designed around algorithms and explores up-and-coming techniques for solving partial word problems as well as the future direction of research. This five-part book begins with a section on basics that covers terminology, the compatibility of partial words, and combinatorial properties of words. The book then focuses on three important concepts of periodicity on partial words: period, weak period, and local period. The next part describes a linear time algorithm to test primitivity on partial words and extends the results on unbordered words to unbordered partial words while the following section introduces some important properties of pcodes, details a variety of ways of defining and analyzing pcodes, and shows that the pcode property is decidable using two different techniques. In the final part, the author solves various equations on partial words, presents binary and ternary correlations, and covers unavoidable sets of partial words.
Setting the tone for future research in this field, this book lucidly develops the central ideas and results of combinatorics on partial words.
preface Basics Preliminaries on Partial Words Alphabets, letters, and words Partial functions and partial words Periodicity Factorizations of partial words Recursion and induction on partial words Containment and compatibility Combinatorial Properties of Partial Words Conjugacy Commutativity PERIODICITY Fine and Wilf's Theorem The case of zero or one hole The case of two or three holes Special partial words Graphs associated with partial words The main result Related results Critical Factorization Theorem Orderings The zero-hole case The main result: First version The main result: Second version Tests Guibas and Odlyzko's Theorem The zero-hole case The main result The algorithm PRIMITIVITY Primitive Partial Words Testing primitivity on partial words Counting primitive partial words Exact periods First counting method Second counting method Existence of primitive partial words Unbordered Partial Words Concatenations of prefixes More results on concatenations of prefixes Critical factorizations Conjugates CODING Pcodes of Partial Words Binary relations Pcodes Pcodes and monoids Prefix and suffix orderings Border ordering Commutative ordering Circular pcodes Deciding the Pcode Property First algorithm Second algorithm FURTHER TOPICS Equations on Partial Words The equation xm ? yn The equation x2 ? ymz The equation xmyn ? zp Correlations of Partial Words Binary and ternary correlations Characterizations of correlations Distributive lattices Unavoidable Sets of Partial Words Unavoidable sets Classifying unavoidable sets of size two The case where k = 1 and l = 1 The case where k = 1 and l = 2 Larger values of k and l Solutions to Selected Exercises References Index Numerous Exercises as well as Website and Bibliographic Notes appear at the end of each chapter.