Logo image
Back
Crucial words for abelian powers
Conference paper   Open access   Peer reviewed

Crucial words for abelian powers

A. Glen, B.V. Halldórsson and S. Kitaev
Developments in Language Theory V, Vol.5583, pp.264-275
Springer Verlag
Proceedings of the 13th International Conference on Developments in Language Theory (Stuttgart, Germany, pp. 264-275, 30/06/2009–03/07/2009)
2009
DOI: https://doi.org/10.1007/978-3-642-02737-6_21
pdf
crucial_words_for_abelian_powers.pdfDownloadView
Author’s Version Open Access
url
Link to Published Version *Subscription may be requiredView

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 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 avoiding abelian k-th powers. This construction gives the minimal length for k=2 and k=3.

Details

Metrics

176 File views/ downloads
68 Record Views
Logo image