ON THE GROWTH RATES OF COMPLEXITY OF THRESHOLD LANGUAGES / Shur Arseny M.,Gorbunova Irina A. // RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. - 2010. - V. 44, l. 1, SI. - P. 175-192.

ISSN/EISSN:

0988-3754 / нет данных

Type:

Article; Proceedings Paper

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 (alpha) over cap approximate to 1.242 as k tends to infinity.

Author keywords:

Power-free languages; Dejean's conjecture; threshold languages; combinatorial complexity; growth rate DEJEANS CONJECTURE; WORDS

DOI:

10.1051/ita/2010012

Web of Science ID:

ISI:000274411700012

Соавторы в МНС:

—

Другие поля

Поле	Значение
Month	JAN-MAR
Note	12th Mons Theoretical Computer Science Conference, Mons, BELGIUM, AUG 27-30, 2008
Publisher	EDP SCIENCES S A
Address	17, AVE DU HOGGAR, PA COURTABOEUF, BP 112, F-91944 LES ULIS CEDEX A, FRANCE
Language	English
Keywords-Plus	DEJEANS CONJECTURE; WORDS
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	Arseny.Shur@usu.ru
Number-of-Cited-References	18
Journal-ISO	Rairo-Theor. Inform. Appl.
Doc-Delivery-Number	554BY