AbelianSquares < CoWiki

CoWiki Web>Avoidance>AvoidingAbelianPowers>AbelianSquares (2012-03-10, StepanHolub) (raw view)

Abelian squares are avoidable over four-letter alphabet as shown by V. Keränen in
<div style="padding-left: 30px;">
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
</div>

Keränen's infinite word is given as the fixed point of a 85-uniform morphism  g<sub>85</sub>  defined by:

g<sub>85</sub>(a)=abcacdcbcdcadcdbdabacabadbabcbdbcbacbcdcacbabdabacadcbcdcacdbcbacbcd</br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; cacdcbdcdadbdcbca

g<sub>85</sub>(b)=&#963;(h(a))

g<sub>85</sub>(c)=&#963;<sup>2</sup>(h(a))

g<sub>85</sub>(d)=&#963;<sup>3</sup>(h(a))

where &#963; is a cyclic permutation of letters:

&#963;: a &#8614; b, b &#8614; c, c &#8614; d, d &#8614; a 

In 
<div style="padding-left: 30px;">
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
</div>

another similar morphism g<sub>98</sub> generating abelian-square-free word is given by:

g<sub>98</sub>(a)=abcacdcbcdcadbdcbdbabcbdcacbabdbabcabdadcdadbdcbd </br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 
babdbcbacbcdbabdcdbdcacdbcbacbcdcacdcbdcdadbdcbca

More such morphisms are given in
<div style="padding-left: 30px;">
Veikko Keränen: _A powerful abelian square-free substitution over 4 letters_, Theor. Comput. Sci. *410* (38-40): 3893-3900 (2009)
</div>

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:
<div align=center>
_c(n)_ >(12<sup>1/109</sup>)<sup>n-50</sup>&sim; 1.02306<sup>n-50</sup>
</div>

-- Main.StepanHolub - 10 Mar 2012

Topic revision: r3 - 2012-03-10 - StepanHolub

CoWiki

CoWiki Web
CoWiki Web Home
Changes
Index
Search

Webs
- AIMAS
- CERAS
- CF
- CoWiki
- CrySP
- External
- Faqtest
- HCI
- Himrod
- ISG
- Main
- Multicore
- Sandbox
- TWiki
- TestNewSandbox
- TestWebS
- UW

My links
- People
- CERAS
- WatForm
- Tetherless lab
- Ubuntu Main.HowTo
- eDocs
- RGG NE notes
- RGG
- CS infrastructure
- Grad images

Edit