Catalog Home Page

Crucial words for abelian powers

Glen, A., Halldórsson, B.V. and Kitaev, S. (2009) Crucial words for abelian powers. In: Proceedings of the 13th International Conference on Developments in Language Theory, 30 June - 3 July, Stuttgart, Germany, pp. 264-275.

[img] PDF - Authors' Version
Download (171kB)
    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 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.

    Publication Type: Conference Paper
    Murdoch Affiliation: School of Chemical and Mathematical Science
    Publisher: Springer Verlag
    Copyright: © 2009 Springer Berlin Heidelberg.
    Notes: Crucial words for abelian powers (with Bjarni V. Halldórsson, Sergey Kitaev), in: V. Diekert et al. (Eds.), Proceedings of the 13th International Conference on Developments in Language Theory - DLT 2009 (Stuttgart, Germany), June 30 - July 3, 2009, Lecture Notes in Computer Science, vol. 5583, Springer-Verlag, Berlin, 2009, pp. 264-275.
    URI: http://researchrepository.murdoch.edu.au/id/eprint/3801
    Item Control Page

    Downloads

    Downloads per month over past year