New Abelian Square-Free DT0L-Languages over 4 Letters
Veikko Keränen · 2003
In 1906 Axel Thue [34] started the systematic study of structures in words. Consequently, he studied basic objects of theoretical computer science long before the invention of the computer or DNA. In 1961 Paul Erdös [13] raised the question whether abelian squares can be avoided in infinitely long words. In 1992, we presented in [19], see also [20–23], an abelian square-free (a-2-free) endomorphism g85 on the four letter alphabet S4 = {a, b, c, d}. The size of g85, i.e. |g85 (abcd)|, is equal to 4×85. Until now, all known methods for constructing arbitrarily long a-2-free words on S4 have been based on the structure of this g85; see Arturo Carpi [4–6]. In this paper, we report of a completely new endomorphism g98 of S4 * , the iteration of which produces an infinite abelian square-free word. The size of g98 is 4×98, and the image words for letters are constructed, in part, differently from the case of g85. For g85 they were directly obtained by permutating letters cyclically. The endomorphism g98 is not an a-2-free endomorphism itself, since it does not preserve the a-2-freeness of all words of length 7. However, g98 can be used together with g85 to produce a-2-free DT0L-languages of unlimited size. Here DT0L-languages mean deterministic context-independent Lindenmayer languages produced by using compositions of endomorphisms – so called tables; see [32, p.188].