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

On k-Abelian Avoidability

Mari Huova, Juhani Karhumäki, On k-Abelian Avoidability. In: Juhani Karhumäki, Yuri Matiyasevich (Eds.), Combinatorics and graph theory. Part IV, 402, 170–182 , POMI, 2012.

Abstract:

We consider a recently defined notion of k-abelian equivalence of words by giving some basic results and concentrating on avoidability problems. This equivalence relation counts the numbers of factors of length k for a fixed natural number k. We ask for the size of the smallest alphabet for which k-abelian squares and cubes can be avoided, respectively. For 2-abelian squares this is four – as in the case of abelian words, while for 2-abelian cubes we have only strong evidence that the size is two – as it is in the case of words. In addition, we point out a few properties of morphisms supporting the view that it might be difficult to find solutions to our questions by simply iterating a morphism.

BibTeX entry:

@INPROCEEDINGS{inpHuKa12a,
  title = {On k-Abelian Avoidability},
  booktitle = {Combinatorics and graph theory. Part IV},
  author = {Huova, Mari and Karhumäki, Juhani},
  series = {402},
  editor = {Karhumäki, Juhani and Matiyasevich, Yuri},
  publisher = {POMI},
  pages = {170–182  },
  year = {2012},
  keywords = {combinatorics on words,  k-abelian equivalence, avoidability},
}

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

Edit publication