no. 3
On the D0L repetition threshold
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 44 (2010) no. 3, pp. 281-292

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.

DOI : 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},
     pages = {281--292},
     year = {2010},
     publisher = {EDP Sciences},
     volume = {44},
     number = {3},
     doi = {10.1051/ita/2010015},
     mrnumber = {2761520},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2010015/}
}
TY  - JOUR
AU  - Goldstein, Ilya
TI  - On the D0L repetition threshold
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2010
SP  - 281
EP  - 292
VL  - 44
IS  - 3
PB  - EDP Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2010015/
DO  - 10.1051/ita/2010015
LA  - en
ID  - ITA_2010__44_3_281_0
ER  - 
%0 Journal Article
%A Goldstein, Ilya
%T On the D0L repetition threshold
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2010
%P 281-292
%V 44
%N 3
%I EDP Sciences
%U https://www.numdam.org/articles/10.1051/ita/2010015/
%R 10.1051/ita/2010015
%G en
%F 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) no. 3, pp. 281-292. doi: 10.1051/ita/2010015

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

[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

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

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

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

[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

[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

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

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

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

[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

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

[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

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

[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

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

[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

[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

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

[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

[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

Cité par Sources :