On the D0L repetition threshold
Goldstein, Ilya
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010), p. 281-292 / Harvested from Numdam
Access to full text
Full (PDF)
Full (DJVU)

The repetition threshold is a measure of the extent to which there need to be consecutive (partial) repetitions of finite words within infinite words over alphabets of various sizes. Dejean's Conjecture, which has been recently proven, provides this threshold for all alphabet sizes. Motivated by a question of Krieger, we deal here with the analogous threshold when the infinite word is restricted to be a D0L word. Our main result is that, asymptotically, this threshold does not exceed the unrestricted threshold by more than a little.

Publié le : 2010-01-01
DOI : https://doi.org/10.1051/ita/2010015
Classification:  68R15 
@article{ITA_2010__44_3_281_0,
     author = {Goldstein, Ilya},
     title = {On the D0L repetition threshold},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     volume = {44},
     year = {2010},
     pages = {281-292},
     doi = {10.1051/ita/2010015},
     mrnumber = {2761520},
     zbl = {pre05822253},
     language = {en},
     url = {http://dml.mathdoc.fr/item/ITA_2010__44_3_281_0}
}

Goldstein, Ilya. On the D0L repetition threshold. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) pp. 281-292. doi : 10.1051/ita/2010015. http://gdmltest.u-ga.fr/item/ITA_2010__44_3_281_0/

[1] A. Carpi, Multidimensional unrepetitive configurations. Theor. Comput. Sci. 56 (1988) 233-241. | Zbl 0649.68073

[2] A. Carpi, On the repetition threshold for large alphabets, in Proc. MFCS, Lecture Notes in Computer Science 3162. Springer-Verlag (2006) 226-237 | Zbl 1132.68515

[3] J. Cassaigne, Complexité et facteurs spéciaux, Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl 0921.68065

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

[5] J. Currie and N. Rampersad, Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl. 43 (2009) 775-778. | Zbl 1192.68497

[6] J. Currie and N. Rampersad, A proof of Dejean's conjecture. pre-print

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

[8] A. Ehrenfeucht and G. Rozenberg, On the subword complexity of D0L-languages with a constant distribution. Inf. Process. Lett. 13 (1981) 108-113. | Zbl 0546.68062

[9] A. Ehrenfeucht and G. Rozenberg, On the subword complexity of square-free D0L-languages. Theor. Comput. Sci. 16 (1981) 25-32. | Zbl 0481.68073

[10] A. Ehrenfeucht and G. Rozenberg, On the subword complexity of locally catenative D0L-languages. Inf. Process. Lett. 16 (1983) 7-9. | Zbl 0501.68038

[11] A. Ehrenfeucht and G. Rozenberg, On the subword complexity of m-free D0L-languages. Inf. Process. Lett. 17 (1983) 121-124. | Zbl 0526.68067

[12] A. Ehrenfeucht and G. Rozenberg, On the size of the alphabet and the subword complexity of square-free D0L languages. Semigroup Forum 26 (1983) 215-223. | Zbl 0512.68058

[13] A. Frid, Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci. 306 (2003) 535-542. | Zbl 1070.68068

[14] A. Frid, On uniform DOL words. STACS (1998) 544-554.

[15] A. Frid, On the frequency of factors in a D0L word. Journal of Automata, Languages and Combinatorics 3 (1998) 29-41. | Zbl 0912.68116

[16] I. Goldstein, Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci. 410 (2009) 2084-2098 | Zbl 1168.68025

[17] D. Krieger, Critical exponents and stabilizers of infinite words, Ph.D. thesis, Waterloo, Ontario, Canada (2008). Available from http://uwspace.uwaterloo.ca/handle/10012/3599.

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

[19] B. Mossé, Reconnaissabilité des substitutions et complixité des suites automatiques. Bulletin de la Société Mathématique de France 124 (1996) 329-346. | Numdam | Zbl 0855.68072

[20] J. Moulin-Ollagnier, Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters. Theor. Comput. Sci. 95 (1992) 187-205. | Zbl 0745.68085

[21] 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. | Zbl 0536.68072

[22] T. Tapsoba, Automates calculant la complexité des suites automatiques. Journal de Théorie des nombres de Bordeaux 6 (1994) 127-124. | Numdam | Zbl 0815.11015

[23] 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. | JFM 39.0283.01

[24] 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-418. | JFM 44.0462.01