Mathematics – Combinatorics
Scientific paper
2011-04-21
Mathematics
Combinatorics
6 pages, 3 figures, Dagstuhl Seminar Combinatorial and Algorithmic Aspects of Sequence Processing (11081)
Scientific paper
We introduce new avoidability problems for words by considering equivalence relations, k-abelian equivalences, which lie properly in between equality and commutative equality, i.e. abelian equality. For two k-abelian equivalent words the numbers of occurrences of different factors of length k coincide and the prefixies (resp. suffixies) of length k-1 are equal as well. The size of the smallest alphabet avoiding 2-repetitions of words, i.e. squares, is three and for abelian squares it is four. It follows that for 2-abelian squares this size has to be three or four. Similarly, the size of the smallest alphabet where 2-abelian cubes, i.e. 3-repetitions, can be avoided is two or three, because cubes (resp. abelian cubes) are avoidable in binary (resp. ternary) alphabet. We show that for 2-abelian squares the required size is four, as in the case of abelian squares. The longest 2-abelian square-free ternary word is of length 537. The question for 2-abelian cubes is open. Though, we have computational evidence that the size would be two, since there exists 2-abelian cube-free binary word of length 100 000, meaning that the 2-abelian case would behave like that of words.
Huova Mari
Karhumäki Juhani
No associations
LandOfFree
Observations and Problems on k-abelian avoidability does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Observations and Problems on k-abelian avoidability, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Observations and Problems on k-abelian avoidability will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-178590