Amy Glen ; Bjarni V. Halldorsson ; Sergey Kitaev - Crucial abelian k-power-free words

dmtcs:513 - Discrete Mathematics & Theoretical Computer Science, January 1, 2010, Vol. 12 no. 5 -
Crucial abelian k-power-free words

Authors: Amy Glen 1; Bjarni V. Halldorsson ORCID-iD2; Sergey Kitaev ORCID-iD3

  • 1 Department of Mathematics and Statistics [Perth]
  • 2 Reykjavík University
  • 3 The Mathematics Institute, Reyjavik University

In 1961, Erdos asked whether or not there exist words of arbitrary length over a fixed finite alphabet that avoid patterns of the form XX' where X' is a permutation of X (called abelian squares). This problem has since been solved in the affirmative in a series of papers from 1968 to 1992. Much less is known in the case of abelian k-th powers, i.e., words of the form X1X2 ... 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 (2004), who showed that a minimal crucial word over an n-letter alphabet A(n) = \1, 2, ..., n\ avoiding abelian squares has length 4n - 7 for n >= 3. Extending this result, we prove that a minimal crucial word over A(n) 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 A(n) avoiding abelian k-th powers. This construction gives the minimal length for k = 2 and k = 3. For k >= 4 and n >= 5, we provide a lower bound for the length of crucial words over A(n) avoiding abelian k-th powers.

Volume: Vol. 12 no. 5
Section: Combinatorics
Published on: January 1, 2010
Imported on: March 26, 2015
Keywords: pattern avoidance,abelian square-free word,abelian cube-free word,abelian power,crucial word,Zimin word,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Linked publications - datasets - softwares

Source : ScholeXplorer IsRelatedTo ARXIV math/0205217
Source : ScholeXplorer IsRelatedTo DOI 10.1016/j.jcta.2003.12.003
Source : ScholeXplorer IsRelatedTo DOI 10.48550/arxiv.math/0205217
  • 10.1016/j.jcta.2003.12.003
  • math/0205217
  • 10.48550/arxiv.math/0205217
Crucial words and the complexity of some extremal problems for sets of prohibited words

Consultation statistics

This page has been seen 593 times.
This article's PDF has been downloaded 264 times.