Restivo, Antonio; Salemi, Sergio 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 Cited in 26 Documents MSC: 20M05 Free semigroups, generators and relations, word problems 68Q45 Formal languages and automata Keywords:overlap free words PDF BibTeX XML