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)
- Institution
- The University of North Carolina at Greensboro (UNCG )
- Web Site: http://library.uncg.edu/
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 http://www.uncg.edu/mat/research/cft2/ has been established for automated use of the program.
Partial words and the critical factorization theorem revisited
PDF (Portable Document Format)
569 KB
Created on 6/27/2011
Views: 2035
Additional Information
- Publication
- Theoretical Computer Science
- Language: English
- Date: 2007
- Keywords
- Word, Partial word, Period, Weak period, Local period