Crucial words for abelian powers

Details Crucial words for abelian powers Crucial words for abelian powers

2008-12-27

arxiv.org/abs/0812.4730v1

Lecture Notes in Computer Science, vol. 5583, Springer-Verlag, Berlin, 2009, pp. 264-275

Mathematics

Combinatorics

14 pages

Scientific paper

10.1007/978-3-642-02737-6_21

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 X_1X_2...X_k where X_i is a permutation of X_1 for 2<= i <= k. When k=2 or 3, one deals with "abelian squares" and "abelian cubes", respectively. In 2004 (arXiv:math/0205217), Evdokimov and Kitaev showed that a minimal crucial word over an n-letter alphabet A_n = {1,2,..., n} avoiding abelian squares has length 4n-7 for n >= 3. In this paper we show that a minimal crucial word over A_n 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 A_n 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 A_n avoiding abelian k-th powers.

Affiliated with

Also associated with

No associations

Rating

Crucial words for abelian powers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Crucial words for abelian powers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Crucial words for abelian powers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191550