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

Strongly k-Abelian Repetitions

Mari Huova, Aleksi Saarela, Strongly k-Abelian Repetitions. In: Juhani Karhumäki, Arto Lepistö, Luca Q. Zamboni (Eds.), Combinatorics on Words, LNCS 8079, 161–168, Springer, 2013.

Abstract:

We consider with a new point of view the notion of $n$th powers in connection with the $k$-abelian equivalence of words. For a fixed natural number $k$, words $u$ and $v$ are $k$-abelian equivalent if every factor of length at most $k$ occurs in $u$ as many times as in $v$. The usual abelian equivalence coincides with 1-abelian equivalence. Usually $k$-abelian squares are defined as words $w$ for which there exist non-empty $k$-abelian equivalent words $u$ and $v$ such that $w=uv$. The new way to consider $k$-abelian $n$th powers is to say that a word is \textit{strongly $k$-abelian $n$th power} if it is $k$-abelian equivalent to an $n$th power. We prove that strongly $k$-abelian $n$th powers are not avoidable on any alphabet for any numbers $k$ and $n$. In the abelian case this is easy, but for $k > 1$ the proof is not trivial.

BibTeX entry:

@INPROCEEDINGS{inpHuSa13a,
  title = {Strongly k-Abelian Repetitions},
  booktitle = {Combinatorics on Words},
  author = {Huova, Mari and Saarela, Aleksi},
  volume = {8079},
  series = {LNCS},
  editor = {Karhumäki, Juhani and Lepistö, Arto and Zamboni, Luca Q.},
  publisher = {Springer},
  pages = {161–168},
  year = {2013},
  keywords = {k-abelian equivalence, nth powers, avoidability},
}

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

Edit publication