Square-Free Words and Idempotent Semigroups
Jean Berstel, Christophe Reutenauer · Cambridge University Press eBooks · 1997
Introduction The investigation of words includes a series of combinatorial studies with rather surprising conclusions that can be summarized roughly by the following statement: Each sufficiently long word over a finite alphabet behaves locally in a regular fashion. That is to say, an arbitrary word, subject only to the constraint that it be sufficiently long, possesses some regularity. This claim becomes meaningful only if one specifies the kind of regularities that are intended, of course. The discovery and the analysis of these unavoidable regularities constitute a major topic in the combinatorics of words. A typical example is furnished by van der Waerden's theorem. It should not be concluded that any sufficiently long word is globally regular. On the contrary, the existence of unavoidable regularities leads to the dual question of avoidable regularities: properties not automatically shared by all sufficiently long words. For such a property there exist infinitely many words (finiteness of the alphabet is supposed) that do not satisfy it. The present chapter is devoted mainly to the study of one such property. A square is a word of the form uu , with u a nonempty word. A word contains a square if one of its factors is a square; otherwise, the word is called square-free . For instance, abcacbacbc contains the square acbacb , and abcacbabcb is square-free. The answer to the question of whether every sufficiently long word contains a square is no, provided the alphabet has at least three letters.