On the growth rates of complexity of threshold languages

Arseny M. Shur; Irina A. Gorbunova

RAIRO - Theoretical Informatics and Applications (2010)

  • Volume: 44, Issue: 1, page 175-192
  • ISSN: 0988-3754

Abstract

top
Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant α ^ ≈ 1 . 242 as k tends to infinity.

How to cite

top

Shur, Arseny M., and Gorbunova, Irina A.. "On the growth rates of complexity of threshold languages." RAIRO - Theoretical Informatics and Applications 44.1 (2010): 175-192. <http://eudml.org/doc/250770>.

@article{Shur2010,
abstract = { Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant $\hat\{\alpha\}\approx1.242$ as k tends to infinity.},
author = {Shur, Arseny M., Gorbunova, Irina A.},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Power-free languages; Dejean's conjecture; threshold languages; combinatorial complexity; growth rate.; power-free languages; growth rate},
language = {eng},
month = {2},
number = {1},
pages = {175-192},
publisher = {EDP Sciences},
title = {On the growth rates of complexity of threshold languages},
url = {http://eudml.org/doc/250770},
volume = {44},
year = {2010},
}

TY - JOUR
AU - Shur, Arseny M.
AU - Gorbunova, Irina A.
TI - On the growth rates of complexity of threshold languages
JO - RAIRO - Theoretical Informatics and Applications
DA - 2010/2//
PB - EDP Sciences
VL - 44
IS - 1
SP - 175
EP - 192
AB - Threshold languages, which are the (k/(k–1))+-free languages over k-letter alphabets with k ≥ 5, are the minimal infinite power-free languages according to Dejean's conjecture, which is now proved for all alphabets. We study the growth properties of these languages. On the base of obtained structural properties and computer-assisted studies we conjecture that the growth rate of complexity of the threshold language over k letters tends to a constant $\hat{\alpha}\approx1.242$ as k tends to infinity.
LA - eng
KW - Power-free languages; Dejean's conjecture; threshold languages; combinatorial complexity; growth rate.; power-free languages; growth rate
UR - http://eudml.org/doc/250770
ER -

References

top
  1. F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82.  
  2. A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151.  
  3. C. Choffrut, J. Karhumäki, Combinatorics of words, edited by G. Rosenberg and A. Salomaa. Handbook of formal languages, Vol. 1, Chap. 6. Springer, Berlin (1997) 329–438.  
  4. M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inform. Process. Lett.67 (1998) 111–117.  
  5. J.D. Currie, N. Rampersad, Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl.43 (2009) 775–778.  
  6. J.D. Currie, N. Rampersad, A proof of Dejean's conjecture,  URIhttp://arxiv.org/PS_cache/arxiv/pdf/0905/0905.1129v3.pdf
  7. F. Dejean, Sur un Theoreme de Thue. J. Combin. Theory Ser. A13 (1972) 90–99.  
  8. A. Ehrenfeucht and G. Rozenberg, On subword complexities of homomorphic images of languages. RAIRO Inform. Theor.16 (1982) 303–316.  
  9. M. Lothaire, Combinatorics on words. Addison-Wesley (1983).  
  10. M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28 (2007) 876–890.  
  11. J. Moulin-Ollagnier, Proof of Dejean's Conjecture for Alphabets with 5, 6, 7, 8, 9, 10 and 11 Letters. Theoret. Comput. Sci.95 (1992) 187–205.  
  12. J.-J. Pansiot, À propos d'une conjecture de F. Dejean sur les répétitions dans les mots. Discrete Appl. Math.7 (1984) 297–311.  
  13. M. Rao, Last Cases of Dejean's Conjecture, accepted to WORDS'2009.  
  14. A.M. Shur, Rational approximations of polynomial factorial languages. Int. J. Found. Comput. Sci.18 (2007) 655–665.  
  15. A.M. Shur, Combinatorial complexity of regular languages, Proceedings of CSR'2008. Lect. Notes Comput. Sci.5010 (2008) 289–301.  
  16. A.M. Shur, Growth rates of complexity of power-free languages. Submitted to Theoret. Comput. Sci. (2008).  
  17. A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl.42 (2008) 647–655.  
  18. A. Thue, Über unendliche Zeichenreihen, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana7 (1906) 1–22.  

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.