ABSTRACT
Over the last few years the discrete mathematics and theoretical computer science communities have witnessed an explosive growth in the area of algorithmic combinatorics on words. Words, or strings of symbols over a finite alphabet, are natural objects in several research areas including automata and formal language theory, coding theory, and theory of algorithms. Molecular biology has stimulated considerable interest in the study of partial words which are strings that may contain a number of “do not know” symbols or “holes.” The motivation behind the notion of a partial word is the comparison of genes. Alignment of two such strings can be viewed as a construction of two partial words that are said to be compatible in a sense that will be discussed in Chapter 1. While a word can be described by a total function, a partial word can be described by a partial function. More precisely, a partial word of length n over a finite alphabet A is a partial function from {0, . . . , n − 1} into A. Elements of {0, . . . , n− 1} without an image are called holes (a word is just a partial word without holes). Research in combinatorics on partial words is underway [10, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 105, 111, 124, 130, 131] and promises a rich theory as well as substantial impact especially in molecular biology, nano-technology, data communication, and DNA computing [104]. Partial words are currently being considered, in particular, for finding good encodings for DNA computations. Courses, covering different sets of topics, are already being taught at some universities. The time seems right for a book that develops, in a clear manner, some of the central ideas and results of this area, as well as sets the tone of research for the next several years. This book on algorithmic combinatorics on partial words addresses precisely this need.
