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

On the Unavoidability of k-Abelian Squares in Pure Morphic Words

Mari Huova, Juhani Karhumäki, On the Unavoidability of k-Abelian Squares in Pure Morphic Words. Journal of Integer Sequences 16, 1–11, 2013.

Abstract:

We consider a recently defined notion of k-abelian equivalence of words by con-
centrating on avoidability problems. The equivalence class of a word depends on the
number of occurrences of different factors of length k for a fixed natural number k and
the prefix of the word. We show that over a ternary alphabet, k-abelian squares cannot
be avoided in pure morphic words for any natural number k. Nevertheless, computa-
tional experiments support the conjecture that even 3-abelian squares can be avoided
over a ternary alphabet. This illustrates that the simple but widely used method to
produce infinite words by iterating a single morphism is not powerful enough with
k-abelian avoidability questions.

BibTeX entry:

@ARTICLE{jHuKa13a,
  title = {On the Unavoidability of k-Abelian Squares in Pure Morphic Words},
  author = {Huova, Mari and Karhumäki, Juhani},
  journal = {Journal of Integer Sequences},
  volume = {16},
  pages = {1–11},
  year = {2013},
  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 1

Edit publication