Dejean’s conjecture holds for 𝖭≥27
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 775-778.

We show that Dejean’s conjecture holds for n≥27. This brings the final resolution of the conjecture by the approach of Moulin Ollagnier within range of the computationally feasible.

DOI : 10.1051/ita/2009017
Classification : 68R15
Mots-clés : Dejean's conjecture, repetitions in words, fractional exponent 
@article{ITA_2009__43_4_775_0,
     author = {Currie, James and Rampersad, Narad},
     title = {Dejean{\textquoteright}s conjecture holds for $\sf {N\ge 27}$},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {775--778},
     publisher = {EDP-Sciences},
     volume = {43},
     number = {4},
     year = {2009},
     doi = {10.1051/ita/2009017},
     mrnumber = {2589992},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2009017/}
}
TY  - JOUR
AU  - Currie, James
AU  - Rampersad, Narad
TI  - Dejean’s conjecture holds for $\sf {N\ge 27}$
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2009
SP  - 775
EP  - 778
VL  - 43
IS  - 4
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2009017/
DO  - 10.1051/ita/2009017
LA  - en
ID  - ITA_2009__43_4_775_0
ER  - 
%0 Journal Article
%A Currie, James
%A Rampersad, Narad
%T Dejean’s conjecture holds for $\sf {N\ge 27}$
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2009
%P 775-778
%V 43
%N 4
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2009017/
%R 10.1051/ita/2009017
%G en
%F ITA_2009__43_4_775_0
Currie, James; Rampersad, Narad. Dejean’s conjecture holds for $\sf {N\ge 27}$. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 43 (2009) no. 4, pp. 775-778. doi : 10.1051/ita/2009017. https://www.numdam.org/articles/10.1051/ita/2009017/

[1] F.J. Brandenburg, Uniformly growing k-th powerfree homomorphisms. Theoret. Comput. Sci. 23 (1983) 69-82. | MR | Zbl

[2] J. Brinkhuis, Non-repetitive sequences on three symbols. Quart. J. Math. Oxford 34 (1983) 145-149. | MR | Zbl

[3] A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137-151. | MR | Zbl

[4] J.D. Currie and N. Rampersad, Dejean’s conjecture holds for n≥30. Theoret. Comput. Sci. 410 (2009) 2885-2888. | MR | Zbl

[5] J.D. Currie, N. Rampersad, A proof of Dejean's conjecture, http://arxiv.org/pdf/0905.1129v3. | Zbl

[6] F. Dejean, Sur un théorème de Thue. J. Combin. Theory Ser. A 13 (1972) 90-99. | MR | Zbl

[7] L. Ilie, P. Ochem and J. Shallit, A generalization of repetition threshold. Theoret. Comput. Sci. 345 (2005) 359-369. | MR | Zbl

[8] D. Krieger, On critical exponents in fixed points of non-erasing morphisms. Theoret. Comput. Sci. 376 (2007) 70-88. | MR | Zbl

[9] M. Lothaire, Combinatorics on Words, Encyclopedia of Mathematics and its Applications 17. Addison-Wesley, Reading (1983). | MR | Zbl

[10] F. Mignosi and G. Pirillo, Repetitions in the Fibonacci infinite word. RAIRO-Theor. Inf. Appl. 26 (1992) 199-204. | Numdam | MR | Zbl

[11] M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin. 28 (2007) 876-890. | MR | Zbl

[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. | MR | Zbl

[13] 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. | MR | Zbl

[14] M. Rao, Last cases of Dejean's Conjecture, http://www.labri.fr/perso/rao/publi/dejean.ps.

[15] A. Thue, Über unendliche Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM

[16] A. Thue, Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen. Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiana 1 (1912) 1-67. | JFM

  • Pape-Lange, Julian Tight Upper Bounds on Distinct Maximal (Sub-)Repetitions in Highly Compressible Strings, International Journal of Foundations of Computer Science, Volume 34 (2023) no. 02n03, p. 321 | DOI:10.1142/s0129054122440075
  • Currie, James D.; Mol, Lucas The undirected repetition threshold and undirected pattern avoidance, Theoretical Computer Science, Volume 866 (2021), p. 56 | DOI:10.1016/j.tcs.2021.03.010
  • Currie, James D.; Mol, Lucas The Undirected Repetition Threshold, Combinatorics on Words, Volume 11682 (2019), p. 145 | DOI:10.1007/978-3-030-28796-2_11
  • Richomme, Gwenaël Minimal critical exponent of quasiperiodic words, Theoretical Computer Science, Volume 548 (2014), p. 117 | DOI:10.1016/j.tcs.2014.06.039
  • Shur, Arseny M. Growth of Power-Free Languages over Large Alphabets, Theory of Computing Systems, Volume 54 (2014) no. 2, p. 224 | DOI:10.1007/s00224-013-9512-x
  • Shur, Arseny M. Growth properties of power-free languages, Computer Science Review, Volume 6 (2012) no. 5-6, p. 187 | DOI:10.1016/j.cosrev.2012.09.001
  • GORBUNOVA, IRINA A.; SHUR, ARSENY M. ON PANSIOT WORDS AVOIDING 3-REPETITIONS, International Journal of Foundations of Computer Science, Volume 23 (2012) no. 08, p. 1583 | DOI:10.1142/s0129054112400631
  • Gorbunova, Irina A.; Shur, Arseny M. On Pansiot Words Avoiding 3-Repetitions, Electronic Proceedings in Theoretical Computer Science, Volume 63 (2011), p. 138 | DOI:10.4204/eptcs.63.19
  • Fiorenzi, Francesca; Ochem, Pascal; Vaslet, Elise Bounds for the generalized repetition threshold, Theoretical Computer Science, Volume 412 (2011) no. 27, p. 2955 | DOI:10.1016/j.tcs.2010.10.009
  • Rao, Michaël Last cases of Dejean’s conjecture, Theoretical Computer Science, Volume 412 (2011) no. 27, p. 3010 | DOI:10.1016/j.tcs.2010.06.020
  • Kolpakov, Roman; Rao, Michaël On the number of Dejean words over alphabets of 5, 6, 7, 8, 9 and 10 letters, Theoretical Computer Science, Volume 412 (2011) no. 46, p. 6507 | DOI:10.1016/j.tcs.2011.08.006
  • Shur, Arseny M.; Gorbunova, Irina A. On the growth rates of complexity of threshold languages, RAIRO - Theoretical Informatics and Applications, Volume 44 (2010) no. 1, p. 175 | DOI:10.1051/ita/2010012
  • Goldstein, Ilya On the D0L Repetition Threshold, RAIRO - Theoretical Informatics and Applications, Volume 44 (2010) no. 3, p. 281 | DOI:10.1051/ita/2010015

Cité par 13 documents. Sources : Crossref