A generator of morphisms for infinite words
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, p. 427-441
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.
DOI : https://doi.org/10.1051/ita:2006020
Classification:  68R15
@article{ITA_2006__40_3_427_0,
author = {Ochem, Pascal},
title = {A generator of morphisms for infinite words},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
publisher = {EDP-Sciences},
volume = {40},
number = {3},
year = {2006},
pages = {427-441},
doi = {10.1051/ita:2006020},
zbl = {1110.68122},
mrnumber = {2269202},
language = {en},
url = {http://http://www.numdam.org/item/ITA_2006__40_3_427_0}
}

Ochem, Pascal. A generator of morphisms for infinite words. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 40 (2006) no. 3, pp. 427-441. doi : 10.1051/ita:2006020. http://www.numdam.org/item/ITA_2006__40_3_427_0/

[1] K.A. Baker, G.F. Mcnulty and W. Taylor, Growth Problems for Avoidable Words. Theoret. Comput. Sci. 69 (1989) 319-345. | Zbl 0693.68039

[2] D.R. Bean, A. Ehrenfeucht, G.F. Mcnulty, Avoidable Patterns in Strings of Symbols. Pacific J. Math. 85 (1979) 261-294. | Zbl 0428.05001

[3] J. Berstel, Axel Thue's Papers on Repetitions in Words: a Translation. Number 20 in Publications du Laboratoire de Combinatoire et d'Informatique Mathématique. Université du Québec à Montréal (February 1995).

[4] J. Cassaigne, Motifs évitables et régularité dans les mots, Thèse de Doctorat, Université Paris VI (Juillet 1994).

[5] R.J. Clark. Avoidable formulas in combinatorics on words, Ph.D. Thesis, University of California, Los Angeles (2001).

[6] J.D. Currie, Open problems in pattern avoidance. Amer. Math. Monthly 100 (1993) 790-793. | Zbl 0798.68139

[7] F. Dejean, Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90-99. | Zbl 0245.20052

[8] A.S. Fraenkel and R.J. Simpson, How many squares must a binary sequence contain? Elect. J. Combin. 2 (1995) #R2. | MR 1309124 | Zbl 0816.11007

[9] L. Ilie, P. Ochem and J.O. Shallit, A generalization of Repetition Threshold. Theoret. Comput. Sci. 345 (2005) 359-369. | MR 2171619 | Zbl 1079.68082

[10] J. Karhumäki and J. O. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 105 (2004) 335-347. | Zbl 1065.68080

[11] M. Lothaire, Algebraic Combinatorics on Words. Cambridge Univ. Press (2002). | MR 1905123 | Zbl 1001.68093

[12] J. Moulin-Ollagnier, Proof of Dejean's conjecture for alphabets with 5,6,7,8,9,10 and 11 letters. Theoret. Comput. Sci. 95 (1992) 187-205. | Zbl 0745.68085

[13] J.-J. Pansiot, A propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Disc. Appl. Math. 7 (1984) 297-311. | Zbl 0536.68072

[14] N. Rampersad, J. Shallit and M.-W. Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | Zbl 1099.68080

[15] J.O. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words. Internat. J. Found. Comput. Sci. 15 (2004) 317-327. | Zbl 1067.68119

[16] A. Thue, Über unendliche Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 7 (1906), 1-22. Reprinted in Selected Mathematical Papers of Axel Thue, edited by T. Nagell, Universitetsforlaget, Oslo (1977) 139-158. | JFM 39.0283.01

[17] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen, Norske vid. Selsk. Skr. Mat. Nat. Kl. 1 (1912) 1-67. Reprinted in Selected Mathematical Papers of Axel Thue, edited by T. Nagell, Universitetsforlaget, Oslo (1977) 413-478. | JFM 43.0162.07

[18] A.I. Zimin, Blocking sets of terms. Math. USSR Sbornik 47 (1984) 353-364. English translation. | Zbl 0599.20106