## Overlap free words on two symbols.(English)Zbl 0572.20038

Automata on infinite words, Ec. Printemps Inf. Théor., Le Mont Dore 1984, Lect. Notes Comput. Sci. 192, 198-206 (1985).
[For the entire collection see Zbl 0563.00019.]
Overlap free words over two symbols are considered. These are words in the free monoid $$\{a,b\}^*$$ having no factors of the form xvxvx, where x is in $$\{$$ a,b$$\}$$ and v in $$\{a,b\}^*$$. In particular, it is shown that the number of overlap free words grows polynomially when the length increases.
Reviewer: T.J.Harju

### MSC:

 20M05 Free semigroups, generators and relations, word problems 68Q45 Formal languages and automata

### Keywords:

overlap free words

Zbl 0563.00019