Partial words and the critical factorization theorem

摘要

The study of combinatorics on words, or finite sequences of symbols from a finite alphabet, finds applications in several areas of biology, computer science, mathematics, and physics. Molecular biology, in particular, has stimulated considerable interest in the study of combinatorics on partial words that are sequences that may have a number of "do not know" symbols also called "holes". This paper is devoted to a fundamental result on periods of words, the critical factorization theorem, which states that the period of a word is always locally detectable in at least one position of the word resulting in a corresponding critical factorization. Here, we describe precisely the class of partial words w with one hole for which the weak period is locally detectable in at least one position of w. Our proof provides an algorithm which computes a critical factorization when one exists. A World Wide Web server interface at http://www.uncg.edu/mat/cft/ has been established for automated use of the program. (c) 2004 Elsevier Inc. All rights reserved.