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


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


Zbl 0563.00019