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

Abstract

top
We prove two cases of a strong version of Dejean's conjecture involving extremal letter frequencies. The results are that there exist an infinite 5 4 + -free word over a 5 letter alphabet with letter frequency 1 6 and an infinite 6 5 + -free word over a 6 letter alphabet with letter frequency 1 5 .

How to cite

top

Chalopin, 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
  1. A. Carpi, On Dejeans conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151.  Zbl1124.68087
  2. 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.  
  3. M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28(3) (2007) 876–890.  Zbl1111.68096
  4. F. Dejean, Sur un théorème de Thue. J. Combin. Theor. Ser. A13 (1972) 90–99.  Zbl0245.20052
  5. 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
  6. R. Kolpakov, G. Kucherov and Y. Tarannikov, On repetition-free binary words of minimal density. Theoret. Comput. Sci.218 (1999) 161–175.  Zbl0916.68118
  7. 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
  8. P. Ochem, Letter frequency in infinite repetition-free words. Theoret. Comput. Sci.380 (2007) 388–392.  Zbl1115.68124
  9. 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).  
  10. 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
  11. C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words. Electron. J. Comb.11 (2004) #R14.  Zbl1104.68090
  12. 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

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.