Algorithmic combinatorics on partial words / Francine Blanchet-Sadri.

Saved in:
Bibliographic Details
Published: Boca Raton, FL : Chapman & Hall/CRC, c2008.
Online Access:
Main Author:
Blanchet-Sadri, Francine
Series:Discrete mathematics and its applications
Subjects:
Computer algorithms.
Computer science > Mathematics.
Combinatorial analysis.
Format: Book
Algorithmic combinatorics on partial words /
Table of Contents:
  • I. Basics
  • 1. Preliminaries on Partial Words
  • 1.1. Alphabets, letters, and words
  • 1.2. Partial functions and partial words
  • 1.3. Periodicity
  • 1.4. Factorizations of partial words
  • 1.5. Recursion and induction on partial words
  • 1.6. Containment and compatibility
  • 2. Combinatorial Properties of Partial Words
  • 2.1. Conjugacy
  • 2.2. Commutativity
  • II. Periodicity
  • 3. Fine and Wilf's Theorem
  • 3.1. The case of zero or one hole
  • 3.2. The case of two or three holes
  • 3.3. Special partial words
  • 3.4. Graphs associated with partial words
  • 3.5. The main result
  • 3.6. Related results
  • 4. Critical Factorization Theorem
  • 4.1. Orderings
  • 4.2. The zero-hole case
  • 4.3. The main result: First version
  • 4.4. The main result: Second version
  • 4.5. Tests
  • 5. Guibas and Odlyzko's Theorem
  • 5.1. The zero-hole case
  • 5.2. The main result
  • 5.3. The algorithm
  • III. Primitivity
  • 6. Primitive Partial Words
  • 6.1. Testing primitivity on partial words
  • 6.2. Counting primitive partial words
  • 6.3. Exact periods
  • 6.4. First counting method
  • 6.5. Second counting method
  • 6.6. Existence of primitive partial words
  • 7. Unbordered Partial Words
  • 7.1. Concatenations of prefixes
  • 7.2. More results on concatenations of prefixes
  • 7.3. Critical factorizations
  • 7.4. Conjugates
  • IV. Coding
  • 8. Pcodes of Partial Words
  • 8.1. Binary relations
  • 8.2. Pcodes
  • 8.3. Pcodes and monoids
  • 8.4. Prefix and suffix orderings
  • 8.5. Border ordering
  • 8.6. Commutative ordering
  • 8.7. Circular pcodes
  • 9. Deciding the Pcode Property
  • 9.1. First algorithm
  • 9.2. Second algorithm
  • V. Further Topics
  • 10. Equations on Partial Words
  • 10.1. The equation x[superscript m] [actual symbol not reproducible] y[superscript n]
  • 10.2. The equation x[superscript 2 ] [actual symbol not reproducible] y[superscript m]z
  • 10.3. The equation x[superscript m]y[superscript n] [actual symbol not reproducible] z[superscript p]
  • 11. Correlations of Partial Words
  • 11.1. Binary and ternary correlations
  • 11.2. Characterizations of correlations
  • 11.3. Distributive lattices
  • 11.4. Irreducible period sets
  • 11.5. Counting correlations Exercises
  • 12. Unavoidable Sets of Partial Words
  • 12.1. Unavoidable sets
  • 12.2. Classifying unavoidable sets of size two
  • 12.3. The case where k = 1 and l = 1
  • 12.4. The case where k = 1 and l = 2
  • 12.5. Larger values of k and l.

Similar Items