Abelian squares are avoidable over four-letter alphabet as shown by V. Keränen in
V. Keränen, Abelian squares are avoidable on 4 letters, Proc. ICALP '92, Lecture Notes in Comp. Sci. 623, Springer, Berlin (1992), pp. 41–52

Keränen's infinite word is given as the fixed point of a 85-uniform morphism g85 defined by:





where σ is a cyclic permutation of letters:

σ: a ↦ b, b ↦ c, c ↦ d, d ↦ a


V. Keränen, New abelian square-free DT0L-languages over 4 letters, Proceedings of the Fifth International Arctic Seminar (IAS 2002, May 15 - 17, 2002, Murmansk, Russia), Murmansk State Pedagogical Institute, 2002

another similar morphism g98 generating abelian-square-free word is given by:


More such morphisms are given in

Veikko Keränen: A powerful abelian square-free substitution over 4 letters, Theor. Comput. Sci. 410 (38-40): 3893-3900 (2009)

All the morphisms can be seen and downloaded at http://south.rotol.ramk.fi/keranen/words2007/a2f.html

It is also known that the number c(n) of abelian-square-free words of length n grows exponentially:

c(n) >(121/109)n-50∼ 1.02306n-50

-- StepanHolub - 10 Mar 2012

Edit | Attach | Watch | Print version | History: r3 < r2 < r1 | Backlinks | Raw View | Raw edit | More topic actions
Topic revision: r3 - 2012-03-10 - StepanHolub
This site is powered by the TWiki collaboration platform Powered by PerlCopyright © 2008-2024 by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback