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.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 pp. 264-275.

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

Item 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 Item Control Page

Downloads

Downloads per month over past year