Algorithmic Combinatorics on Partial Words

Front Cover
CRC Press, Nov 19, 2007 - Mathematics - 392 pages
1 Review
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.

 

What people are saying - Write a review

We haven't found any reviews in the usual places.

Contents

List of Figures
9
Preface
13
BASICS
23
Preliminaries on Partial Words
25
Combinatorial Properties of Partial Words
43
PERIODICITY
61
Fine and Wilf s Theorem
63
Critical Factorization Theorem
93
CODING
223
Pcodes of Partial Words
225
Deciding the Pcode Property
257
FURTHER TOPICS
279
Equations on Partial Words
281
Correlations of Partial Words
297
Unavoidable Sets of Partial Words
325
Solutions to Selected Exercises
345

Guibas and Odlyzkos Theorem
117
PRIMITIVITY
155
Primitive Partial Words
157
Unbordered Partial Words
199
References
369
Index
379
Copyright

Other editions - View all

Common terms and phrases

Bibliographic information