Extremal infinite overlap-free binary words
The electronic journal of combinatorics, Tome 5 (1998)
Let $\overline{\bf t}$ be the infinite fixed point, starting with $1$, of the morphism $\mu: 0 \rightarrow 01$, $1 \rightarrow 10$. An infinite word over $\lbrace 0, 1 \rbrace$ is said to be overlap-free if it contains no factor of the form $axaxa$, where $a \in \lbrace 0,1 \rbrace$ and $x \in \lbrace 0,1 \rbrace^*$. We prove that the lexicographically least infinite overlap-free binary word beginning with any specified prefix, if it exists, has a suffix which is a suffix of $\overline{\bf t}$. In particular, the lexicographically least infinite overlap-free binary word is $001001 \overline{\bf t}$.
@article{10_37236_1365,
author = {Jean-Paul Allouche and James Currie and Jeffrey Shallit},
title = {Extremal infinite overlap-free binary words},
journal = {The electronic journal of combinatorics},
year = {1998},
volume = {5},
doi = {10.37236/1365},
zbl = {0890.68107},
url = {http://geodesic.mathdoc.fr/articles/10.37236/1365/}
}
Jean-Paul Allouche; James Currie; Jeffrey Shallit. Extremal infinite overlap-free binary words. The electronic journal of combinatorics, Tome 5 (1998). doi: 10.37236/1365
Cité par Sources :