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 -free ternary words and -free 4-ary words. Finally we give small morphisms for binary words containing only the squares , and and for binary words avoiding large squares and fractional repetitions.
@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}, pages = {427--441}, publisher = {EDP-Sciences}, volume = {40}, number = {3}, year = {2006}, doi = {10.1051/ita:2006020}, mrnumber = {2269202}, zbl = {1110.68122}, language = {en}, url = {http://www.numdam.org/articles/10.1051/ita:2006020/} }
TY - JOUR AU - Ochem, Pascal TI - A generator of morphisms for infinite words JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2006 SP - 427 EP - 441 VL - 40 IS - 3 PB - EDP-Sciences UR - http://www.numdam.org/articles/10.1051/ita:2006020/ DO - 10.1051/ita:2006020 LA - en ID - ITA_2006__40_3_427_0 ER -
%0 Journal Article %A Ochem, Pascal %T A generator of morphisms for infinite words %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2006 %P 427-441 %V 40 %N 3 %I EDP-Sciences %U http://www.numdam.org/articles/10.1051/ita:2006020/ %R 10.1051/ita:2006020 %G en %F 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/articles/10.1051/ita:2006020/
[1] Growth Problems for Avoidable Words. Theoret. Comput. Sci. 69 (1989) 319-345. | Zbl
, and ,[2] Avoidable Patterns in Strings of Symbols. Pacific J. Math. 85 (1979) 261-294. | Zbl
, , ,[3] 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] Motifs évitables et régularité dans les mots, Thèse de Doctorat, Université Paris VI (Juillet 1994).
,[5] Avoidable formulas in combinatorics on words, Ph.D. Thesis, University of California, Los Angeles (2001).
.[6] Open problems in pattern avoidance. Amer. Math. Monthly 100 (1993) 790-793. | Zbl
,[7] Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90-99. | Zbl
,[8] How many squares must a binary sequence contain? Elect. J. Combin. 2 (1995) #R2. | MR | Zbl
and ,[9] A generalization of Repetition Threshold. Theoret. Comput. Sci. 345 (2005) 359-369. | MR | Zbl
, and ,[10] Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A 105 (2004) 335-347. | Zbl
and ,[11] Algebraic Combinatorics on Words. Cambridge Univ. Press (2002). | MR | Zbl
,[12] 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
,[13] A propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Disc. Appl. Math. 7 (1984) 297-311. | Zbl
,[14] Avoiding large squares in infinite binary words. Theoret. Comput. Sci. 339 (2005) 19-34. | Zbl
, and ,[15] Simultaneous avoidance of large squares and fractional powers in infinite binary words. Internat. J. Found. Comput. Sci. 15 (2004) 317-327. | Zbl
,[16] Ü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
,[17] Ü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
,[18] Blocking sets of terms. Math. USSR Sbornik 47 (1984) 353-364. English translation. | Zbl
,Cité par Sources :