Algorithmic Combinatorics on Partial Words

Free Standard Shipping

Purchasing Options

ISBN 9781420060928
Cat# C6092



SAVE 20%

eBook (VitalSource)
ISBN 9781420060935
Cat# CE6092



SAVE 30%

eBook Rentals

Other eBook Options:


  • Presents algorithms in English followed by pseudo code to facilitate implementation of the algorithms
  • Provides abundant worked examples and diagrams to illustrate concepts
  • Offers links to many web interfaces that have been established for automated use of the programs related to the book
  • Contains numerous exercises, including programming exercises, at the end of each chapter as well as selected solutions at the back of the book
  • 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

    Preliminaries on Partial Words
    Alphabets, letters, and words
    Partial functions and partial words
    Factorizations of partial words
    Recursion and induction on partial words
    Containment and compatibility
    Combinatorial Properties of Partial Words
    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
    The zero-hole case
    The main result: First version
    The main result: Second version
    Guibas and Odlyzko’s Theorem
    The zero-hole case
    The main result
    The algorithm
    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
    Pcodes of Partial Words
    Binary relations
    Pcodes and monoids
    Prefix and suffix orderings
    Border ordering
    Commutative ordering
    Circular pcodes
    Deciding the Pcode Property
    First algorithm
    Second algorithm
    Equations on Partial Words
    The equation xmyn
    The equation x2ymz
    The equation xmynzp
    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
    Numerous Exercises as well as Website and Bibliographic Notes appear at the end of each chapter.