Simple Search

Query:

Enter a query and click »Search«...

Format:

Display: entries per page entries

Zbl 1184.68341
Shur, Arseny M.; Gorbunova, Irina A.
On the growth rates of complexity of threshold languages. (English)
[J] RAIRO, Theor. Inform. Appl. 44, No. 1, 175-192 (2010). ISSN 0988-3754; ISSN 1290-385X/e

Summary: Threshold languages, which are the $(k/(k-1))^+$-free languages over $k$-letter alphabets with $k\geq 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 \approx 1.242$ as $k$ tends to infinity.

MSC 2000:: *68Q70 Algebraic theory of automata
68R15 Combinatorics on words

Keywords: power-free languages; Dejean's conjecture; threshold languages; combinatorial complexity; growth rate

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Article Journal Journal Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Simple Search

Zentralblatt MATH Berlin [Germany]