# A generator of morphisms for infinite words

RAIRO - Theoretical Informatics and Applications (2006)

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

## Access Full Article

top## Abstract

top## How to cite

topOchem, 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- K.A. Baker, G.F. McNulty and W. Taylor, Growth Problems for Avoidable Words. Theoret. Comput. Sci.69 (1989) 319–345.
- D.R. Bean, A. Ehrenfeucht, G.F. McNulty, Avoidable Patterns in Strings of Symbols. Pacific J. Math.85 (1979) 261–294.
- 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).
- J. Cassaigne, Motifs évitables et régularité dans les mots, Thèse de Doctorat, Université Paris VI (Juillet 1994).
- R.J. Clark. Avoidable formulas in combinatorics on words, Ph.D. Thesis, University of California, Los Angeles (2001).
- J.D. Currie, Open problems in pattern avoidance. Amer. Math. Monthly100 (1993) 790–793.
- F. Dejean, Sur un théorème de Thue. J. Combin. Theory. Ser. A13 (1972) 90–99.
- A.S. Fraenkel and R.J. Simpson, How many squares must a binary sequence contain? Elect. J. Combin.2 (1995) #R2.
- L. Ilie, P. Ochem and J.O. Shallit, A generalization of Repetition Threshold. Theoret. Comput. Sci.345 (2005) 359-369.
- J. Karhumäki and J. O. Shallit, Polynomial versus exponential growth in repetition-free binary words. J. Combin. Theory Ser. A105 (2004) 335–347.
- M. Lothaire, Algebraic Combinatorics on Words. Cambridge Univ. Press (2002).
- 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.
- 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.
- N. Rampersad, J. Shallit and M.-W. Wang, Avoiding large squares in infinite binary words. Theoret. Comput. Sci.339 (2005) 19–34.
- J.O. Shallit, Simultaneous avoidance of large squares and fractional powers in infinite binary words. Internat. J. Found. Comput. Sci.15 (2004) 317–327.
- 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.
- 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.
- A.I. Zimin, Blocking sets of terms. Math. USSR Sbornik47 (1984) 353–364. English translation.

## Citations in EuDML Documents

top- Pascal Ochem, Binary words avoiding the pattern AABBCABBA
- Robert Mercaş, Pascal Ochem, Alexey V. Samsonov, Arseny M. Shur, Binary patterns in binary cube-free words: Avoidability and growth
- Pascal Ochem, Elise Vaslet, Repetition thresholds for subdivided graphs and trees
- Pascal Ochem, Elise Vaslet, Repetition thresholds for subdivided graphs and trees

## NotesEmbed ?

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