# Dejean's conjecture and letter frequency

Jérémie Chalopin; Pascal Ochem

RAIRO - Theoretical Informatics and Applications (2008)

- Volume: 42, Issue: 3, page 477-480
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topChalopin, Jérémie, and Ochem, Pascal. "Dejean's conjecture and letter frequency." RAIRO - Theoretical Informatics and Applications 42.3 (2008): 477-480. <http://eudml.org/doc/250327>.

@article{Chalopin2008,

abstract = {
We prove two cases of a strong version of Dejean's conjecture
involving extremal letter frequencies. The results are that there
exist an infinite $\left(\{\frac\{5\}\{4\}^+\}\right)$-free word over a 5 letter
alphabet with letter frequency $\frac\{1\}\{6\}$ and an infinite
$\left(\{\frac\{6\}\{5\}^+\}\right)$-free word over a 6 letter alphabet with
letter frequency $\frac\{1\}\{5\}$.
},

author = {Chalopin, Jérémie, Ochem, Pascal},

journal = {RAIRO - Theoretical Informatics and Applications},

language = {eng},

month = {6},

number = {3},

pages = {477-480},

publisher = {EDP Sciences},

title = {Dejean's conjecture and letter frequency},

url = {http://eudml.org/doc/250327},

volume = {42},

year = {2008},

}

TY - JOUR

AU - Chalopin, Jérémie

AU - Ochem, Pascal

TI - Dejean's conjecture and letter frequency

JO - RAIRO - Theoretical Informatics and Applications

DA - 2008/6//

PB - EDP Sciences

VL - 42

IS - 3

SP - 477

EP - 480

AB -
We prove two cases of a strong version of Dejean's conjecture
involving extremal letter frequencies. The results are that there
exist an infinite $\left({\frac{5}{4}^+}\right)$-free word over a 5 letter
alphabet with letter frequency $\frac{1}{6}$ and an infinite
$\left({\frac{6}{5}^+}\right)$-free word over a 6 letter alphabet with
letter frequency $\frac{1}{5}$.

LA - eng

UR - http://eudml.org/doc/250327

ER -

## References

top- A. Carpi, On Dejeans conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151. Zbl1124.68087
- C. Choffrut and J. Karhumäki, Combinatorics of words, in Handbook of Formal Languages, edited by G. Rozenberg and A. Salomaa, Springer-Verlag (1997) 329–438.
- M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28(3) (2007) 876–890. Zbl1111.68096
- F. Dejean, Sur un théorème de Thue. J. Combin. Theor. Ser. A13 (1972) 90–99. Zbl0245.20052
- A. Khalyavin. The minimal density of a letter in an infinite ternary square-free word is 883/3215. J. Integer Sequences10 (2007) 07.6.5. Zbl1140.11304
- R. Kolpakov, G. Kucherov and Y. Tarannikov, On repetition-free binary words of minimal density. Theoret. Comput. Sci.218 (1999) 161–175. Zbl0916.68118
- 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. Zbl0745.68085
- P. Ochem, Letter frequency in infinite repetition-free words. Theoret. Comput. Sci.380 (2007) 388–392. Zbl1115.68124
- P. Ochem and T. Reix, Upper bound on the number of ternary square-free words, in Workshop on Words and Automata (WOWA'06). St. Petersburg, Russia, June 7 (2006).
- J.-J. Pansiot, À propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math.7 (1984) 297–311. Zbl0536.68072
- C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words. Electron. J. Comb.11 (2004) #R14. Zbl1104.68090
- Y. Tarannikov, The minimal density of a letter in an infinite ternary square-free word is 0.2746... J. Integer Sequences5 (2002) 02.2.2. Zbl1121.11303

## Citations in EuDML Documents

top## NotesEmbed ?

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