• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

Observations and Problems on k-abelian Avoidability

Mari Huova, Juhani Karhumäki, Observations and Problems on k-abelian Avoidability. In: Maxime Crochemore, Lila Kari, Mehryar Mohri, Dirk Nowotka (Eds.), Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081), 2215-2219, Daghstuhl Publishing, 2011.

Abstract:

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.

BibTeX entry:

@INPROCEEDINGS{inpHuKa11a,
  title = {Observations and Problems on k-abelian Avoidability},
  booktitle = {Combinatorial and Algorithmic Aspects of Sequence Processing (Dagstuhl Seminar 11081)},
  author = {Huova, Mari and Karhumäki, Juhani},
  editor = {Crochemore, Maxime and Kari, Lila and Mohri, Mehryar and Nowotka, Dirk},
  publisher = {Daghstuhl Publishing},
  pages = {2215-2219},
  year = {2011},
}

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication