A generator of morphisms for infinite words

Pascal Ochem

RAIRO - Theoretical Informatics and Applications (2006)

  • Volume: 40, Issue: 3, page 427-441
  • ISSN: 0988-3754

Abstract

top
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 7 4 + -free ternary words and 7 5 + -free 4-ary words. Finally we give small morphisms for binary words containing only the squares 2, 12 and (01)² and for binary words avoiding large squares and fractional repetitions.

How to cite

top

Ochem, Pascal. "A generator of morphisms for infinite words." RAIRO - Theoretical Informatics and Applications 40.3 (2006): 427-441. <http://eudml.org/doc/249724>.

@article{Ochem2006,
abstract = { 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 2, 12 and (01)² and for binary words avoiding large squares and fractional repetitions. },
author = {Ochem, Pascal},
journal = {RAIRO - Theoretical Informatics and Applications},
language = {eng},
month = {10},
number = {3},
pages = {427-441},
publisher = {EDP Sciences},
title = {A generator of morphisms for infinite words},
url = {http://eudml.org/doc/249724},
volume = {40},
year = {2006},
}

TY - JOUR
AU - Ochem, Pascal
TI - A generator of morphisms for infinite words
JO - RAIRO - Theoretical Informatics and Applications
DA - 2006/10//
PB - EDP Sciences
VL - 40
IS - 3
SP - 427
EP - 441
AB - 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 2, 12 and (01)² and for binary words avoiding large squares and fractional repetitions.
LA - eng
UR - http://eudml.org/doc/249724
ER -

References

top
  1. K.A. Baker, G.F. McNulty and W. Taylor, Growth Problems for Avoidable Words. Theoret. Comput. Sci.69 (1989) 319–345.  
  2. D.R. Bean, A. Ehrenfeucht, G.F. McNulty, Avoidable Patterns in Strings of Symbols. Pacific J. Math.85 (1979) 261–294.  
  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. Monthly100 (1993) 790–793.  
  7. F. Dejean, Sur un théorème de Thue. J. Combin. Theory. Ser. A13 (1972) 90–99.  
  8. A.S. Fraenkel and R.J. Simpson, How many squares must a binary sequence contain? Elect. J. Combin.2 (1995) #R2.  
  9. L. Ilie, P. Ochem and J.O. Shallit, A generalization of Repetition Threshold. Theoret. Comput. Sci.345 (2005) 359-369.  
  10. J. Karhumäki and J. O. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A105 (2004) 335–347.  
  11. M. Lothaire, Algebraic Combinatorics on Words. Cambridge Univ. Press (2002).  
  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.  
  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.  
  14. N. Rampersad, J. Shallit and M.-W. Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci.339 (2005) 19–34.  
  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.  
  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.  
  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.  
  18. A.I. Zimin, Blocking sets of terms. Math. USSR Sbornik47 (1984) 353–364. English translation.  

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.