Skip to Content

Algorithmic Combinatorics on Partial Words

Chapman and Hall/CRC – 2007 – 392 pages

Series: Discrete Mathematics and Its Applications

Purchasing Options:

  • Add to CartHardback: $109.95
    978-1-42-006092-8
    November 19th 2007

Description

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.

Contents

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 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

References

Index

Numerous Exercises as well as Website and Bibliographic Notes appear at the end of each chapter.

Name: Algorithmic Combinatorics on Partial Words (Hardback)Chapman and Hall/CRC 
Description: . 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...
Categories: Combinatorics, Discrete Mathematics, Algorithms & Complexity