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
topHow 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.
- 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.
- F. Dejean, Sur un théorème de Thue. J. Combin. Theor. Ser. A13 (1972) 90–99.
- 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.
- R. Kolpakov, G. Kucherov and Y. Tarannikov, On repetition-free binary words of minimal density. Theoret. Comput. Sci.218 (1999) 161–175.
- 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.
- P. Ochem, Letter frequency in infinite repetition-free words. Theoret. Comput. Sci.380 (2007) 388–392.
- 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.
- C. Richard and U. Grimm, On the entropy and letter frequencies of ternary square-free words. Electron. J. Comb.11 (2004) #R14.
- 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.
Citations in EuDML Documents
topNotesEmbed ?
topYou 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.