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

Problems in Between Words and Abelian Words: k-Abelian Avoidability

Mari Huova, Juhani Karhumäki, Aleksi Saarela, Problems in Between Words and Abelian Words: k-Abelian Avoidability. Theoretical Computer Science 454, 172–177, 2012.

Abstract:

We consider a recently defined notion of k-abelian equivalence of words in connection with avoidability problems. This equivalence relation, for a fixed natural number k, takes into account the numbers of occurrences of the different factors of length k and the prefix and the suffix of length k−1. We search for the smallest alphabet in 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. However, we are able to prove this optimal value only for 8-abelian cubes.

BibTeX entry:

@ARTICLE{jHuKaSa12a,
  title = {Problems in Between Words and Abelian Words: k-Abelian Avoidability},
  author = {Huova, Mari and Karhumäki, Juhani and Saarela, Aleksi},
  journal = {Theoretical Computer Science},
  volume = {454},
  pages = {172–177},
  year = {2012},
  keywords = {Combinatorics on Words,  k-abelian equivalence, Avoidability},
}

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

Publication Forum rating of this publication: level 2

Edit publication