On the growth rates of complexity of threshold languages
Ural State University, Ekaterinburg, Russia; Arseny.Shur@usu.ru
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 as k tends to infinity.
Mathematics Subject Classification: 68Q70 / 68R15
Key words: Power-free languages / Dejean's conjecture / threshold languages / combinatorial complexity / growth rate.
© EDP Sciences, 2010