×

Repetitivity of semigroups and a result of Cassaigne, Currie, Schaeffer and Shallit. (English) Zbl 1399.68079

Summary: The recent remarkable result of J. Cassaigne et al. [J. ACM 61, No. 2, Article No. 10, 17 p. (2014; Zbl 1295.68173)] about the existence of an infinite word without three consecutive factors “of the same sum and size” shows the importance of the theory of “repetitive semigroups” in combinatorics on words. This seems to be an occasion to recall the main definitions and results in the theory of repetitivity (which had been presented in Chapter 4 of [M. Lothaire, Combinatorics on words. Cambridge University Press, Cambridge (1983; Zbl 0514.20045)]). We recall the progress since that time and in the last section we present some applications of the result of Cassaigne et al. [loc. cit.].
In particular, we recall a result we obtained with Stefano Varricchio and the techniques we pioneered with him.

MSC:

68R15 Combinatorics on words
20M05 Free semigroups, generators and relations, word problems
PDFBibTeX XMLCite