# Crucial words for abelian powers

Glen, Amy and Halldorsson, Bjarni and Kitaev, Sergey
(2009)
*Crucial words for abelian powers.*
In:
Developments in Language Theory.
Lecture Notes in Computer Science
.
Springer-Verlag Berlin, pp. 264-275.
ISBN 978-3-642-02736-9

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

ID code: | 49973 |

Keywords: | pattern avoidance, abelian square-free word, abelian cube-free word, abelian power, crucial word, Electronic computers. Computer science, Computational Mathematics |

Subjects: | Science > Mathematics > Electronic computers. Computer science |

Department: | Faculty of Science > Computer and Information Sciences |

Depositing user: | Pure Administrator |

Date deposited: | 21 Oct 2014 14:55 |

Last modified: | 22 Mar 2017 15:49 |

URI: | http://strathprints.strath.ac.uk/id/eprint/49973 |

Export data: |