zbMATH — the first resource for mathematics

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