On the Unavoidability of k-Abelian Squares in Pure Morphic Words
Mari Huova and Juhani Karhumäki
Department of Mathematics and Statistics
University of Turku
We consider a recently defined notion of k-abelian
equivalence of words by concentrating 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
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, computational 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.
Full version: pdf,
(Concerned with sequences
Received July 1 2012;
revised version received October 11 2012.
Published in Journal of Integer Sequences, March 2 2013.
Journal of Integer Sequences home page