# 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

## Access Full Article

top## Abstract

top## How to cite

topShur, 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- F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82. Zbl0508.68051
- A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151. Zbl1124.68087
- 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.
- M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inform. Process. Lett.67 (1998) 111–117. Zbl06590735
- J.D. Currie, N. Rampersad, Dejean's conjecture holds for n ≥ 27. RAIRO-Theor. Inf. Appl.43 (2009) 775–778. Zbl1192.68497
- J.D. Currie, N. Rampersad, A proof of Dejean's conjecture, Zbl1215.68192URIhttp://arxiv.org/PS_cache/arxiv/pdf/0905/0905.1129v3.pdf
- F. Dejean, Sur un Theoreme de Thue. J. Combin. Theory Ser. A13 (1972) 90–99.
- A. Ehrenfeucht and G. Rozenberg, On subword complexities of homomorphic images of languages. RAIRO Inform. Theor.16 (1982) 303–316. Zbl0495.68069
- M. Lothaire, Combinatorics on words. Addison-Wesley (1983). Zbl0514.20045
- M. Mohammad-Noori and J.D. Currie, Dejean's conjecture and Sturmian words. Eur. J. Combin.28 (2007) 876–890. Zbl1111.68096
- 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. Zbl0745.68085
- 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. Zbl0536.68072
- M. Rao, Last Cases of Dejean's Conjecture, accepted to WORDS'2009.
- A.M. Shur, Rational approximations of polynomial factorial languages. Int. J. Found. Comput. Sci.18 (2007) 655–665. Zbl1117.68045
- A.M. Shur, Combinatorial complexity of regular languages, Proceedings of CSR'2008. Lect. Notes Comput. Sci.5010 (2008) 289–301. Zbl1142.68428
- A.M. Shur, Growth rates of complexity of power-free languages. Submitted to Theoret. Comput. Sci. (2008). Zbl1192.68424
- A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl.42 (2008) 647–655. Zbl1149.68055
- A. Thue, Über unendliche Zeichenreihen, Kra. Vidensk. Selsk. Skrifter. I. Mat.-Nat. Kl., Christiana7 (1906) 1–22.

## Citations in EuDML Documents

top## NotesEmbed ?

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