Veikko Keränen

Avoidable Regularities in Strings

Structures, Programs, and Graphics of A-2-Free Strings

From below you may download structural and graphical data of (infinite) abelian square-free strings generated by endomorphisms g85 and g98 over the four letter alphabet {a,b,c,d}. These endomorphisms, and 200 other cases, were found by Veikko Keränen with the help of many RAMK students. Veikko Keränen produced the major part of the related computer graphics.


The endomorphism g85 is an abelian square-free endomorphism. On the other hand, g98 is not an abelian square-free endomorphism as such, though it produces an infinite abelian square-free D0L language. Together g85 and g98 produce an infinite abelian square-free DT0L language.

g85 (abcacd ) represented by 6*85 coloured polyhedra (100 KB jpeg file)

Chain graphics developed with Mathematica
- you may download nb, eps and jpeg files (September 2004)

More chain graphics from April 2005 (based on the experimentation of Mikko Harjuniemi & Petri Kulmala):

g85abcd.jpeg g98abcd.jpeg

g85abcd.eps g98abcd.eps

A review of this topic can be found from this abstract (in English, 1996).

Here is an article in Helsingin Sanomat, 8 June 1996 (in Finnish).

More information can be read from this abstract (in Finnish, 1996).

More links (2000 - 2008):
Structures in g85
(January 2000)
More colourful structures of g85
(October 2004)
Structures of pairs {a,c} and {b,d} in g85^2(a) and g98^2(a)
(January 2005)

A long 2D walk (vectorgram) of g85 (a: left, b: right, c: down, d: up)
Searching for other a-2-free endomorphisms over 4 letters
(January 2000)

The image words of g85 and g98 can be copied as text from here (November 2003)

The image words of g85, g98, and 200 more a2f endomorphisms of length 102 - 115 (May 2008)

Structures in g98 (semi-palindromes) + some forbidden factors (November 2003)
A long 2D walk of g98
(a: left, b: right, c: down, d: up)
The diagonal of g98^2(a) consists completely of a's

The pattern XYXZX applied repeatedly - long forbidden factors obtained

Unfavourable abelian square-free factors over 4 letters with highly nonlinear and quite unintuitive processes (June 2004)

Numbers of abelian square-free words over 4 (and 3) letters of each length up to 60 in case of 4 letters - June 2004,
(up to 70 in case of 3 letters - accepting aa, bb, cc - August 2010)

You may interactively rotate and zoom these LiveGraphics3D representations:

4 letter walks in the diamond lattice (February 2004)

More links (2006):

Programs & Notebooks & Packages for Suppression of Unfavourable Factors in Pattern Avoidance (March 2006)

© 1996-2006 V. Keränen
© 2003 (2D walks) E. Jensen and V. Keränen
© 2004 (3D walks) E. Jensen and V. Keränen

Permission to use, copy, and distribute the material above for any non-commercial purpose is hereby granted without a separate permission, provided that the source is mentioned.