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.