Partial Words and the Critical Factorization Theorem Revisited

F. Blanchet-Sadri and Nathan D. Wetzler


Abstract Paper Implementation

Abstract

In this paper, we consider one of the most fundamental results on periodicity of words, namely the critical factorization theorem. Given a word w and non-empty words u, v satisfying w = uv , the minimal local period associated to the factorization (u, v) is the length of the shortest square at position |u| - 1. The critical factorization theorem shows that for any word, there is always a factorization where the minimal local period is equal to the minimal period (or global period) of the word.

Crochemore and Perrin presented a linear time algorithm (in the length of the word) that finds the critical factorization from the computation of the maximal suffixes of the word with respect to two total orderings on words: the lexicographic ordering related to a fixed total ordering on the alphabet, and the lexicographic ordering obtained by reversing the order of letters in the alphabet. Here, by refining Crochemore and Perrin's algorithm, we give a version of the critical factorization theorem for partial words (such sequences may contain "do not know" symbols, or "holes"). Our proof provides an efficient algorithm which computes a critical factorization when one exists. Our results extend those of Blanchet-Sadri and Duncan for partial words with one hole.

Keywords: Word, partial word, period, weak period, local period.


Visit the NSF Homepage.
Valid XHTML 1.0!

Acknowledgement: This material is based upon work supported by the National Science Foundation under Grant No. DMS-0452020.
Disclaimer: Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the National Science Foundation.

Partial Words Logo
Valid CSS!