# On the D0L Repetition Threshold

RAIRO - Theoretical Informatics and Applications (2010)

- Volume: 44, Issue: 3, page 281-292
- ISSN: 0988-3754

## Access Full Article

top## Abstract

top## How to cite

topGoldstein, Ilya. "On the D0L Repetition Threshold." RAIRO - Theoretical Informatics and Applications 44.3 (2010): 281-292. <http://eudml.org/doc/250786>.

@article{Goldstein2010,

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.
},

author = {Goldstein, Ilya},

journal = {RAIRO - Theoretical Informatics and Applications},

keywords = {finite words; infinite words over alphabets of various sizes},

language = {eng},

month = {10},

number = {3},

pages = {281-292},

publisher = {EDP Sciences},

title = {On the D0L Repetition Threshold},

url = {http://eudml.org/doc/250786},

volume = {44},

year = {2010},

}

TY - JOUR

AU - Goldstein, Ilya

TI - On the D0L Repetition Threshold

JO - RAIRO - Theoretical Informatics and Applications

DA - 2010/10//

PB - EDP Sciences

VL - 44

IS - 3

SP - 281

EP - 292

AB -
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.

LA - eng

KW - finite words; infinite words over alphabets of various sizes

UR - http://eudml.org/doc/250786

ER -

## References

top- A. Carpi, Multidimensional unrepetitive configurations. Theor. Comput. Sci.56 (1988) 233–241. Zbl0649.68073
- A. Carpi, On the repetition threshold for large alphabets, in Proc. MFCS, Lecture Notes in Computer Science 3162. Springer-Verlag (2006) 226–237 Zbl1132.68515
- J. Cassaigne, Complexité et facteurs spéciaux, Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.
- J. Currie and N. Rampersad, Dejean's conjecture holds for n ≥ 30. Theor. Comput. Sci.410 (2009) 2885–2888. Zbl1173.68050
- J. Currie and N. Rampersad, Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl.43 (2009) 775–778. Zbl1192.68497
- J. Currie and N. Rampersad, A proof of Dejean's conjecture. pre-print Zbl1215.68192
- F. Dejean, Sur un théorème de Thue. J. Combin. Theory. Ser. A13 (1972) 90–99. Zbl0245.20052
- A. Ehrenfeucht and G. Rozenberg, On the subword complexity of D0L-languages with a constant distribution. Inf. Process. Lett.13 (1981) 108–113. Zbl0546.68062
- A. Ehrenfeucht and G. Rozenberg, On the subword complexity of square-free D0L-languages. Theor. Comput. Sci.16 (1981) 25–32. Zbl0481.68073
- A. Ehrenfeucht and G. Rozenberg, On the subword complexity of locally catenative D0L-languages. Inf. Process. Lett.16 (1983) 7–9. Zbl0501.68038
- A. Ehrenfeucht and G. Rozenberg, On the subword complexity of m-free D0L-languages. Inf. Process. Lett.17 (1983) 121–124. Zbl0526.68067
- A. Ehrenfeucht and G. Rozenberg, On the size of the alphabet and the subword complexity of square-free D0L languages. Semigroup Forum26 (1983) 215–223. Zbl0512.68058
- A. Frid, Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci.306 (2003) 535–542. Zbl1070.68068
- 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 Combinatorics3 (1998) 29–41. Zbl0912.68116
- I. Goldstein, Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci.410 (2009) 2084–2098 Zbl1168.68025
- D. Krieger, Critical exponents and stabilizers of infinite words, Ph.D. thesis, Waterloo, Ontario, Canada (2008). Available from . URIhttp://uwspace.uwaterloo.ca/handle/10012/3599
- M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Comb.28 (2007) 876–890. Zbl1111.68096
- B. Mossé, Reconnaissabilité des substitutions et complixité des suites automatiques. Bulletin de la Société Mathématique de France124 (1996) 329–346.
- 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. Zbl0745.68085
- 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. Zbl0536.68072
- T. Tapsoba, Automates calculant la complexité des suites automatiques. Journal de Théorie des nombres de Bordeaux6 (1994) 127–124.
- 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.
- 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. Zbl44.0462.01

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.