You are here

Algorithmic Combinatorics on Partial Words

Francine Blanchet-Sadri
Publisher: 
Chapman & Hall/CRC
Publication Date: 
2008
Number of Pages: 
385
Format: 
Hardcover
Series: 
Discrete Mathematics and Its Applications
Price: 
89.95
ISBN: 
9781420060928
Category: 
Monograph
We do not plan to review this book.

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.