# 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.

PDF - Authors' Version Download (171kB) |

*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