A generator of morphisms for infinite words
Ochem, Pascal; Ochem Pascal; LaBRI, Université Bordeaux I, 351, cours de la Libération, 33405 Talence Cedex, France; ochem@labri.fr
Журнал:
RAIRO - Theoretical Informatics and Applications
Дата:
2006
Аннотация:
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 <sup>2</sup>, 1<sup>2</sup> and (01)² and for binary words avoiding large squares and fractional repetitions.
161.3Кб