A generator of morphisms for infinite words

Ochem, Pascal 

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 427-441

Résumé

We present an algorithm which produces, in some cases, infinite words avoiding both large fractional repetitions and a given set of finite words. We use this method to show that all the ternary patterns whose avoidability index was left open in Cassaigne’s thesis are 2-avoidable. We also prove that there exist exponentially many ${\frac{7}{4}}^{+}$-free ternary words and ${\frac{7}{5}}^{+}$-free 4-ary words. Finally we give small morphisms for binary words containing only the squares $0^2$, $1^2$ and ${\left(01\right)}^2$ and for binary words avoiding large squares and fractional repetitions.

Détail

DOI : 10.1051/ita:2006020

Classification : 68R15