Abstract
| Language | English |
|---|---|
| Title of host publication | Developments in Language Theory |
| Subtitle of host publication | 13th International Conference, DLT 2009, Stuttgart, Germany, June 30-July 3, 2009. Proceedings |
| Editors | Volker Diekert, Dirk Nowotka |
| Pages | 264-275 |
| Number of pages | 12 |
| DOIs | |
| Publication status | Published - 2009 |
| Event | 13th Conference on Developments in Language Theory - Stuttgart, Germany Duration: 30 Jun 2009 → 3 Jul 2009 |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer |
| Volume | 5583 |
| ISSN (Print) | 0302-9743 |
Conference
| Conference | 13th Conference on Developments in Language Theory |
|---|---|
| Country | Germany |
| City | Stuttgart |
| Period | 30/06/09 → 3/07/09 |
Fingerprint
Keywords
- pattern avoidance
- abelian square-free word
- abelian cube-free word
- abelian power
- crucial word
Cite this
}
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 proceeding › Conference 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 -