Crucial words for abelian powers

Amy Glen, Bjarni Halldorsson, Sergey Kitaev

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

1 Citation (Scopus)

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.
LanguageEnglish
Title of host publicationDevelopments in Language Theory
Subtitle of host publication13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings
EditorsVolker Diekert, Dirk Nowotka
Pages264-275
Number of pages12
DOIs
Publication statusPublished - 2009
Event13th Conference on Developments in Language Theory - Stuttgart, Germany
Duration: 30 Jun 20093 Jul 2009

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume5583
ISSN (Print)0302-9743

Conference

Conference13th Conference on Developments in Language Theory
CountryGermany
CityStuttgart
Period30/06/093/07/09

Fingerprint

Regular hexahedron
Permutation
Integer
Form

Keywords

  • pattern avoidance
  • abelian square-free word
  • abelian cube-free word
  • abelian power
  • crucial word

Cite this

Glen, A., Halldorsson, B., & Kitaev, S. (2009). Crucial words for abelian powers. In V. Diekert, & D. Nowotka (Eds.), Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings (pp. 264-275). (Lecture Notes in Computer Science; Vol. 5583). https://doi.org/10.1007/978-3-642-02737-6_21
Glen, Amy ; Halldorsson, Bjarni ; Kitaev, Sergey. / Crucial words for abelian powers. Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings. editor / Volker Diekert ; Dirk Nowotka . 2009. pp. 264-275 (Lecture Notes in Computer Science).
@inproceedings{b7c37495df014148934e075ec27d6192,
title = "Crucial words for abelian powers",
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.",
keywords = "pattern avoidance, abelian square-free word, abelian cube-free word, abelian power, crucial word",
author = "Amy Glen and Bjarni Halldorsson and Sergey Kitaev",
year = "2009",
doi = "10.1007/978-3-642-02737-6_21",
language = "English",
isbn = "978-3-642-02736-9",
series = "Lecture Notes in Computer Science",
publisher = "Springer",
pages = "264--275",
editor = "Volker Diekert and {Nowotka }, Dirk",
booktitle = "Developments in Language Theory",

}

Glen, A, Halldorsson, B & Kitaev, S 2009, Crucial words for abelian powers. in V Diekert & D Nowotka (eds), Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings. Lecture Notes in Computer Science, vol. 5583, pp. 264-275, 13th Conference on Developments in Language Theory, Stuttgart, Germany, 30/06/09. https://doi.org/10.1007/978-3-642-02737-6_21

Crucial words for abelian powers. / Glen, Amy; Halldorsson, Bjarni; Kitaev, Sergey.

Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings. ed. / Volker Diekert; Dirk Nowotka . 2009. p. 264-275 (Lecture Notes in Computer Science; Vol. 5583).

Research output: Chapter in Book/Report/Conference proceedingConference contribution book

TY - GEN

T1 - Crucial words for abelian powers

AU - Glen, Amy

AU - Halldorsson, Bjarni

AU - Kitaev, Sergey

PY - 2009

Y1 - 2009

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

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

KW - pattern avoidance

KW - abelian square-free word

KW - abelian cube-free word

KW - abelian power

KW - crucial word

U2 - 10.1007/978-3-642-02737-6_21

DO - 10.1007/978-3-642-02737-6_21

M3 - Conference contribution book

SN - 978-3-642-02736-9

T3 - Lecture Notes in Computer Science

SP - 264

EP - 275

BT - Developments in Language Theory

A2 - Diekert, Volker

A2 - Nowotka , Dirk

ER -

Glen A, Halldorsson B, Kitaev S. Crucial words for abelian powers. In Diekert V, Nowotka D, editors, Developments in Language Theory: 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings. 2009. p. 264-275. (Lecture Notes in Computer Science). https://doi.org/10.1007/978-3-642-02737-6_21