TWiki>
CoWiki Web>Avoidance>AvoidingAbelianPowers>AbelianSquares (2012-03-10, StepanHolub)
EditAttach
CoWiki Web>Avoidance>AvoidingAbelianPowers>AbelianSquares (2012-03-10, StepanHolub) EditAttach Abelian squares are avoidable over four-letter alphabet as shown by V. Keränen in
It is also known that the number c(n) of abelian-square-free words of length n grows exponentially:
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:
g85(a)=abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcd cacdcbdcdadbdcbca
g85(b)=σ(h(a))
g85(c)=σ2(h(a))
g85(d)=σ3(h(a))
where σ is a cyclic permutation of letters:
σ: a ↦ b, b ↦ c, c ↦ d, d ↦ a
In
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:
g98(a)=abcacdcbcdcadbdcbdbabcbdcacbabdbabcabdadcdadbdcbd
babdbcbacbcdbabdcdbdcacdbcbacbcdcacdcbdcdadbdcbca
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 Topic revision: r3 - 2012-03-10 - StepanHolub
 |
|
Copyright © 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