Murdoch University Research Repository

Welcome to the Murdoch University Research Repository

The Murdoch University Research Repository is an open access digital collection of research
created by Murdoch University staff, researchers and postgraduate students.

Learn more

Crucial words for abelian powers

Glen, A.ORCID: 0000-0002-9434-3412, Halldórsson, B. and Kitaev, S. (2009) Crucial words for abelian powers. In: Diekert, V. and Nowotka, D., (eds.) Developments in Language Theory, Lecture Notes in Computer Science, Vol. 5583. Springer, pp. 264-275.

Link to Published Version: http://dx.doi.org/10.1007/978-3-642-02737-6_21
*Subscription may be required

Abstract

Let k ≥ 2 be an integer. An abelian k -th power is a word of the form X 1 X 2 ⋯ X k where X i is a permutation of X 1 for 2 ≤ i ≤ k. In this paper, we consider crucial words for abelian k-th powers, i.e., finite words that avoid abelian k-th powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian k-th power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian k-th powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev [6], who showed that a minimal crucial word over an n-letter alphabet An={1,2,…,n} avoiding abelian squares has length 4n − 7 for n ≥ 3. Extending this result, we prove 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.

Item Type: Book Chapter
Murdoch Affiliation: School of Chemical and Mathematical Science
Publisher: Springer
Copyright: © Springer-Verlag Berlin Heidelberg 2009
Notes: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30--July 3, 2009
URI: http://researchrepository.murdoch.edu.au/id/eprint/19775
Item Control Page Item Control Page