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.
@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}, publisher = {EDP-Sciences}, volume = {44}, number = {3}, year = {2010}, doi = {10.1051/ita/2010015}, mrnumber = {2761520}, language = {en}, url = {http://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 - http://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 http://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, Volume 44 (2010) no. 3, pp. 281-292. doi : 10.1051/ita/2010015. http://www.numdam.org/articles/10.1051/ita/2010015/
[1] Multidimensional unrepetitive configurations. Theor. Comput. Sci. 56 (1988) 233-241. | Zbl
,[2] On the repetition threshold for large alphabets, in Proc. MFCS, Lecture Notes in Computer Science 3162. Springer-Verlag (2006) 226-237 | Zbl
,[3] Complexité et facteurs spéciaux, Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67-88. | Zbl
,[4] Dejean's conjecture holds for n ≥ 30. Theor. Comput. Sci. 410 (2009) 2885-2888. | Zbl
and ,[5] Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl. 43 (2009) 775-778. | Zbl
and ,[6] A proof of Dejean's conjecture. pre-print
and ,[7] Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90-99. | Zbl
,[8] On the subword complexity of D0L-languages with a constant distribution. Inf. Process. Lett. 13 (1981) 108-113. | Zbl
and ,[9] On the subword complexity of square-free D0L-languages. Theor. Comput. Sci. 16 (1981) 25-32. | Zbl
and ,[10] On the subword complexity of locally catenative D0L-languages. Inf. Process. Lett. 16 (1983) 7-9. | Zbl
and ,[11] On the subword complexity of m-free D0L-languages. Inf. Process. Lett. 17 (1983) 121-124. | Zbl
and ,[12] On the size of the alphabet and the subword complexity of square-free D0L languages. Semigroup Forum 26 (1983) 215-223. | Zbl
and ,[13] Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci. 306 (2003) 535-542. | Zbl
,[14] On uniform DOL words. STACS (1998) 544-554.
,[15] On the frequency of factors in a D0L word. Journal of Automata, Languages and Combinatorics 3 (1998) 29-41. | Zbl
,[16] Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci. 410 (2009) 2084-2098 | Zbl
,[17] Critical exponents and stabilizers of infinite words, Ph.D. thesis, Waterloo, Ontario, Canada (2008). Available from http://uwspace.uwaterloo.ca/handle/10012/3599.
,[18] Dejean's conjecture and Sturmian words. Eur. J. Comb. 28 (2007) 876-890. | Zbl
and ,[19] Reconnaissabilité des substitutions et complixité des suites automatiques. Bulletin de la Société Mathématique de France 124 (1996) 329-346. | Numdam | Zbl
,[20] 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] 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] Automates calculant la complexité des suites automatiques. Journal de Théorie des nombres de Bordeaux 6 (1994) 127-124. | Numdam | Zbl
,[23] Ü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] Ü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
,Cited by Sources: