Algorithmic Combinatorics on Partial Words

by Blanchet-Sadri; Francine

• ISBN13: 9781420060928
• ISBN10: 1420060929
• Format: Hardcover
• Copyright: 2007-11-19
• Publisher: Chapman & Hall/

Summary

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.

Table of Contents

Preface	p. 13
Basics	p. 23
Preliminaries on Partial Words	p. 25
Alphabets, letters, and words	p. 25
Partial functions and partial words	p. 27
Periodicity	p. 30
Factorizations of partial words	p. 32
Recursion and induction on partial words	p. 35
Containment and compatibility	p. 36
Exercises	p. 39
Challenging exercises	p. 40
Programming exercises	p. 41
Bibliographic notes	p. 42
Combinatorial Properties of Partial Words	p. 43
Conjugacy	p. 43
The equation xz = zy	p. 43
The equation xz [up arrow] zy	p. 44
Commutativity	p. 48
The equation xy = yx	p. 48
The equation xy [up arrow] yx	p. 48
Exercises	p. 56
Challenging exercises	p. 57
Programming exercises	p. 58
Website	p. 59
Bibliographic notes	p. 59
Periodicity	p. 61
Fine and Wilf's Theorem	p. 63
The case of zero or one hole	p. 63
The case of two or three holes	p. 64
Special partial words	p. 67
p = 1	p. 67
p > 1	p. 71
Graphs associated with partial words	p. 73
The main result	p. 79
Related results	p. 82
Exercises	p. 86
Challenging exercises	p. 88
Programming exercises	p. 89
Websites	p. 90
Bibliographic notes	p. 90
Critical Factorization Theorem	p. 93
Orderings	p. 93
The zero-hole case	p. 96
The main result: First version	p. 98
The main result: Second version	p. 104
Tests	p. 111
Exercises	p. 112
Challenging exercises	p. 113
Programming exercises	p. 114
Websites	p. 115
Bibliographic notes	p. 115
Guibas and Odlyzko's Theorem	p. 117
The zero-hole case	p. 117
The main result	p. 120
The algorithm	p. 145
Exercises	p. 151
Challenging exercises	p. 152
Programming exercises	p. 153
Website	p. 153
Bibliographic notes	p. 154
Primitivity	p. 155
Primitive Partial Words	p. 157
Testing primitivity on partial words	p. 158
Counting primitive partial words	p. 162
Exact periods	p. 164
First counting method	p. 170
Second counting method	p. 174
The one-hole case	p. 178
The two-hole case	p. 181
Existence of primitive partial words	p. 187
Exercises	p. 195
Challenging exercises	p. 196
Programming exercises	p. 196
Website	p. 197
Bibliographic notes	p. 197
Unbordered Partial Words	p. 199
Concatenations of prefixes	p. 200
More results on concatenations of prefixes	p. 207
Critical factorizations	p. 213
Conjugates	p. 216
Exercises	p. 217
Challenging exercises	p. 219
Programming exercises	p. 220
Website	p. 220
Bibliographic notes	p. 221
Coding	p. 223
Pcodes of Partial Words	p. 225
Binary relations	p. 225
Pcodes	p. 229
The class F	p. 233
The class G	p. 234
Pcodes and monoids	p. 236
Prefix and suffix orderings	p. 239
Border ordering	p. 241
Commutative ordering	p. 244
Circular pcodes	p. 249
Exercises	p. 253
Challenging exercises	p. 254
Programming exercises	p. 254
Website	p. 255
Bibliographic notes	p. 255
Deciding the Pcode Property	p. 257
First algorithm	p. 257
Second algorithm	p. 264
Domino technique on words	p. 264
Domino technique on partial words	p. 267
Exercises	p. 275
Challenging exercises	p. 276
Programming exercises	p. 277
Website	p. 277
Bibliographic notes	p. 277
Further Topics	p. 279
Equations on Partial Words	p. 281
The equation x[superscript m up arrow] y[superscript n]	p. 281
The equation x[superscript 2 up arrow] y[superscript m]z	p. 287
The equation x[superscript m]y[superscript n up arrow] z[superscript p]	p. 290
Exercises	p. 292
Challenging exercises	p. 293
Programming exercises	p. 294
Website	p. 294
Bibliographic notes	p. 295
Correlations of Partial Words	p. 297
Binary and ternary correlations	p. 297
Characterizations of correlations	p. 299
Distributive lattices	p. 305
[Delta subscript n] is a distributive lattice	p. 309
[Delta]'[subscript n] is a distributive lattice	p. 309
Irreducible period sets	p. 315
Counting correlations	p. 318
Exercises	p. 321
Challenging exercises	p. 322
Programming exercises	p. 323
Website	p. 323
Bibliographic notes	p. 323
Unavoidable Sets of Partial Words	p. 325
Unavoidable sets	p. 325
Classifying unavoidable sets of size two	p. 328
The case where k = 1 and l = 1	p. 330
The case where k = 1 and l = 2	p. 331
Larger values of k and l	p. 339
Exercises	p. 340
Challenging exercises	p. 341
Programming exercises	p. 342
Website	p. 342
Bibliographic notes	p. 342
Solutions to Selected Exercises	p. 345
References	p. 369
Index	p. 379
Table of Contents provided by Ingram. All Rights Reserved.