Crucial abelian kpowerfree words
Glen, Amy and Halldorsson, Bjarni and Kitaev, Sergey (2010) Crucial abelian kpowerfree words. Discrete Mathematics and Theoretical Computer Science, 12 (5). pp. 8396.
Full text not available in this repository.Request a copyAbstract
In 1961, Erdős 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 kth powers, i.e., words of the form X1X2⋯Xk where Xi is a permutation of X1 for 2 ≤i ≤k. In this paper, we consider crucial words for abelian kth powers, i.e., finite words that avoid abelian kth powers, but which cannot be extended to the right by any letter of their own alphabets without creating an abelian kth power. More specifically, we consider the problem of determining the minimal length of a crucial word avoiding abelian kth powers. This problem has already been solved for abelian squares by Evdokimov and Kitaev (2004), who showed that a minimal crucial word over an nletter alphabet An = {1,2,…, n} avoiding abelian squares has length 4n7 for n≥3. Extending this result, we prove that a minimal crucial word over An avoiding abelian cubes has length 9n13 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 k2(n1)k1 of a crucial word over An avoiding abelian kth 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 An avoiding abelian kth powers.


Item type: Article ID code: 34650 Dates: DateEvent2010PublishedSubjects: Science > Mathematics > Electronic computers. Computer science Department: Faculty of Science > Computer and Information Sciences Depositing user: Pure Administrator Date deposited: 25 Oct 2011 10:15 Last modified: 08 Apr 2024 19:32 Related URLs: URI: https://strathprints.strath.ac.uk/id/eprint/34650