On the growth rates of complexity of threshold languages
Arseny M. Shur, Irina A. Gorbunova · RAIRO - Theoretical Informatics and Applications · 2010
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.