Hostname: page-component-586b7cd67f-vdxz6 Total loading time: 0 Render date: 2024-11-24T14:51:56.780Z Has data issue: false hasContentIssue false
  • English
  • Français

On the D0L Repetition Threshold

Published online by Cambridge University Press:  23 June 2010

Ilya Goldstein
Ilya Goldstein*
Affiliation:
Department of Mathematics, Ben-Gurion University of the Negev, Beer-Sheva 84105, Israel; [email protected]
Get access

Abstract

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.

Keywords

Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 44 , Issue 3 , July 2010 , pp. 281 - 292
Copyright
© EDP Sciences, 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Carpi, A., Multidimensional unrepetitive configurations. Theor. Comput. Sci. 56 (1988) 233–241. CrossRef
A. Carpi, On the repetition threshold for large alphabets, in Proc. MFCS, Lecture Notes in Computer Science 3162. Springer-Verlag (2006) 226–237
Cassaigne, J., Complexité et facteurs spéciaux, Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin 4 (1997) 67–88.
Currie, J. and Rampersad, N., Dejean's conjecture holds for n ≥ 30. Theor. Comput. Sci. 410 (2009) 2885–2888. CrossRef
Currie, J. and Rampersad, N., Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl. 43 (2009) 775–778. CrossRef
J. Currie and N. Rampersad, A proof of Dejean's conjecture. pre-print
Dejean, F., Sur un théorème de Thue. J. Combin. Theory. Ser. A 13 (1972) 90–99. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On the subword complexity of D0L-languages with a constant distribution. Inf. Process. Lett. 13 (1981) 108–113. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On the subword complexity of square-free D0L-languages. Theor. Comput. Sci. 16 (1981) 25–32. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On the subword complexity of locally catenative D0L-languages. Inf. Process. Lett. 16 (1983) 7–9. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On the subword complexity of m-free D0L-languages. Inf. Process. Lett. 17 (1983) 121–124. CrossRef
Ehrenfeucht, A. and Rozenberg, G., On the size of the alphabet and the subword complexity of square-free D0L languages. Semigroup Forum 26 (1983) 215–223. CrossRef
Frid, A., Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci. 306 (2003) 535–542. CrossRef
A Frid, On uniform DOL words. STACS (1998) 544–554.
A. Frid, On the frequency of factors in a D0L word. Journal of Automata, Languages and Combinatorics 3 (1998) 29–41.
Goldstein, I., Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci. 410 (2009) 2084–2098 CrossRef
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.
Mohammad-Noori, M. and Currie, J.D., Dejean's conjecture and Sturmian words. Eur. J. Comb. 28 (2007) 876–890. CrossRef
Mossé, B., Reconnaissabilité des substitutions et complixité des suites automatiques. Bulletin de la Société Mathématique de France 124 (1996) 329–346. CrossRef
Moulin-Ollagnier, J., Proof of Dejean's conjecture for alphabets with 5, 6, 7, 8, 9, 10 and 11 letters. Theor. Comput. Sci. 95 (1992) 187–205. CrossRef
Pansiot, J.-J., A propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Disc. Appl. Math. 7 (1984) 297–311. CrossRef
Tapsoba, T., Automates calculant la complexité des suites automatiques. Journal de Théorie des nombres de Bordeaux 6 (1994) 127–124. CrossRef
Thue, A., Ü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.
Thue, A., Ü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.