Critical Factorization Theorem

In this chapter, we discuss the fundamental critical factorization theorem in the framework of partial words. The critical factorization theorem on full words states that given a word w

and nonempty words u, v satisfying w = uv, the minimal local period associated to the factorization (u, v) of w is the length of the shortest repetition (a square) centered at position |u| − 1. It is easy to see that no minimal local period is longer than the minimal (or global) period of the word. The critical factorization theorem shows that critical factorizations are unavoidable. Indeed, for any string, there is always a factorization whose minimal local period is equal to the global period of the string. In other words, we consider a string a0a1 . . . an−1 and, for any integer i such

that 0 ≤ i < n−1, we look at the shortest repetition centered in this position, that is, we look at the shortest (virtual) suffix of a0a1 . . . ai which is also a (virtual) prefix of ai+1ai+2 . . . an−1. The minimal local period at position i is defined as the length of this shortest square. The critical factorization theorem states, roughly speaking, that the global period of a0a1 . . . an−1 is simply the maximum among all minimal local periods. As an example, consider the word w = babbaab with global period 6. The minimal local periods of w are 2, 3, 1, 6, 1 and 3 which means that the factorization (babb, aab) is critical. In summary, the following table describes the number of holes and section

numbers where the critical factorization theorem is discussed:

0 4.2 arbitrary 4.3, 4.4 and 4.5

A binary relation defined on an arbitrary set S is a subset of S × S. The relation is called reflexive if u u for all u ∈ S; antisymmetric if v v

relation defined on S is called a partial ordering. A total ordering is a partial ordering for which u v or v u holds for all u, v ∈ S. An element u of S (respectively, of a subset X ⊂ S) ordered by is maximal if for all v ∈ S (respectively, v ∈ X) the condition u v implies u = v. Of course each subset of a totally ordered set has at most one maximal element. In this section, we define two total orderings ofW (A), l and r, and state

some lemmas related to them that will be used to prove the main results. First, let the alphabet A be totally ordered by ≺ and let ≺ a for all a ∈ A. • The first total ordering, denoted by ≺l, is simply the lexicographic ordering related to the fixed total ordering on A and is defined as follows: u ≺l v, if either u is a proper prefix of v, or

u = pre(u, v) a x v = pre(u, v) b y

with a, b ∈ A ∪ {} satisfying a ≺l b.1