Journal of Integer Sequences, Vol. 16 (2013), Article 13.2.9

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