Partial words and the critical factorization theorem revisited

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Francine Blanchet-Sadri, Professor (Creator)
The University of North Carolina at Greensboro (UNCG )
Web Site:

Abstract: In this paper, we consider one of the most fundamental results on the periodicity of words, namely the critical factorization theorem. Given a word w and nonempty words u, v satisfying w = uv, the minimal local period associated with 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 whose 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 a 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. A World Wide Web server interface at has been established for automated use of the program.

Additional Information

Theoretical Computer Science
Language: English
Date: 2007
Word, Partial word, Period, Weak period, Local period

Email this document to