Improved bounds on the length of maximal abelian square-free words (Q1883627)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Improved bounds on the length of maximal abelian square-free words |
scientific article |
Statements
Improved bounds on the length of maximal abelian square-free words (English)
0 references
13 October 2004
0 references
Summary: A word is abelian square-free if it does not contain two adjacent subwords which are permutations of each other. Over an alphabet \(\Sigma_k\) on \(k\) letters, an abelian square-free word is maximal if it cannot be extended to the left or right by letters from \(\Sigma_k\) and remain abelian square-free. Michael Korn proved that the length \(\ell (k)\) of a shortest maximal abelian square-free word satisfies \(4k-7\leq \ell(k)\leq 6k-10\) for \(k\geq 6\). In this paper, we refine Korn's methods to show that \(6k-29\leq \ell(k)\leq 6k-12\) for \(k\geq 8\).
0 references