CRUCIAL WORDS FOR ABELIAN POWERS
Amy Glen, Bjarni V. Halldórsson, Sergey Kitaev · 2009
Abstract. A word is crucial with respect to a given set of prohibited words (or simply prohibitions) if it avoids the prohibitions but it cannot be extended to the right by any letter of its alphabet without creating a prohibition. A minimal crucial word is a crucial word of the shortest length. A word W contains an abelian k-th power if W has a factor of the form X1X2... Xk where Xi is a permutation of X1 for 2 ≤ i ≤ k. When k = 2 or 3, one deals with abelian squares and abelian cubes, respectively. Evdokimov and Kitaev [6] have shown that a minimal crucial word over an n-letter alphabet An = {1, 2,..., n} avoiding abelian squares has length 4n − 7 for n ≥ 3. In this paper, we show that a minimal crucial word over An avoiding abelian cubes has length 9n−13 for n ≥ 5, and it has length 2, 5, 11, and 20 for n = 1,2, 3, and 4, respectively. Moreover, for n ≥ 4 and k ≥ 2, we give a construction of length k 2 (n−1)−k −1 of a crucial word over An avoiding abelian k-th powers. This construction gives the minimal length for k = 2 and k = 3. For k ≥ 4 and n ≥ 5, we provide a lower bound for the length of crucial words over An avoiding abelian k-th powers. 1.