On the D0L Repetition Threshold

Ilya Goldstein

RAIRO - Theoretical Informatics and Applications (2010)

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

Abstract

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

How to cite

top

Goldstein, 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
  1. A. Carpi, Multidimensional unrepetitive configurations. Theor. Comput. Sci.56 (1988) 233–241.  
  2. A. Carpi, On the repetition threshold for large alphabets, in Proc. MFCS, Lecture Notes in Computer Science 3162. Springer-Verlag (2006) 226–237  
  3. J. Cassaigne, Complexité et facteurs spéciaux, Journées Montoises (Mons, 1994). Bull. Belg. Math. Soc. Simon Stevin4 (1997) 67–88.  
  4. J. Currie and N. Rampersad, Dejean's conjecture holds for n ≥ 30. Theor. Comput. Sci.410 (2009) 2885–2888.  
  5. J. Currie and N. Rampersad, Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl.43 (2009) 775–778.  
  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. A13 (1972) 90–99.  
  8. A. Ehrenfeucht and G. Rozenberg, On the subword complexity of D0L-languages with a constant distribution. Inf. Process. Lett.13 (1981) 108–113.  
  9. A. Ehrenfeucht and G. Rozenberg, On the subword complexity of square-free D0L-languages. Theor. Comput. Sci.16 (1981) 25–32.  
  10. A. Ehrenfeucht and G. Rozenberg, On the subword complexity of locally catenative D0L-languages. Inf. Process. Lett.16 (1983) 7–9.  
  11. A. Ehrenfeucht and G. Rozenberg, On the subword complexity of m-free D0L-languages. Inf. Process. Lett.17 (1983) 121–124.  
  12. 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.  
  13. A. Frid, Arithmetical complexity of symmetric D0L words. Theor. Comput. Sci.306 (2003) 535–542.  
  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 Combinatorics3 (1998) 29–41.  
  16. I. Goldstein, Asymptotic subword complexity of fixed points of group substitutions. Theor. Comput. Sci.410 (2009) 2084–2098 
  17. 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
  18. M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Comb.28 (2007) 876–890.  
  19. B. Mossé, Reconnaissabilité des substitutions et complixité des suites automatiques. Bulletin de la Société Mathématique de France124 (1996) 329–346.  
  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.  
  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.  
  22. T. Tapsoba, Automates calculant la complexité des suites automatiques. Journal de Théorie des nombres de Bordeaux6 (1994) 127–124.  
  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.  
  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.  

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.