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

Restivo, Antonio; Salemi, Sergio

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