On the Unavoidability of k-Abelian Squares in Pure Morphic Words
Mari Huova and Juhani Karhumäki
Department of Mathematics and Statistics
TUCS
University of Turku
20014 Turku
Finland
Abstract:
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
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, 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,
dvi,
ps,
latex
(Concerned with sequences
A000002
A006156
A010060.)
Received July 1 2012;
revised version received October 11 2012.
Published in Journal of Integer Sequences, March 2 2013.
Return to
Journal of Integer Sequences home page