Growth of Power-Free Languages over Large Alphabets / Shur Arseny M. // THEORY OF COMPUTING SYSTEMS. - 2014. - V. 54, l. 2. - P. 224-243.

ISSN/EISSN:

1432-4350 / 1433-0490

Type:

Article

Abstract:

We study growth properties of power-free languages over finite alphabets. We consider the function alpha(k,beta) whose values are the exponential growth rates of beta-power-free languages over k-letter alphabets and clarify its asymptotic behaviour. Namely, we prove asymptotic formulas for this function for the case beta a parts per thousand yen2 and suggest such formulas for the case beta < 2 on the base of some partial results. All obtained formulas correlate very well with the known numerical bounds on the values of alpha(k,beta).

Author keywords:

Formal languages; Power-free languages; Finite automata; Growth rate DEJEANS CONJECTURE; COMPLEXITY; WORDS; RATES

DOI:

10.1007/s00224-013-9512-x

Web of Science ID:

ISI:000330992200004

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

—

Другие поля

Поле	Значение
Month	FEB
Publisher	SPRINGER
Address	233 SPRING ST, NEW YORK, NY 10013 USA
Language	English
EISSN	1433-0490
Keywords-Plus	DEJEANS CONJECTURE; COMPLEXITY; WORDS; RATES
Research-Areas	Computer Science; Mathematics
Web-of-Science-Categories	Computer Science, Theory \& Methods; Mathematics
Author-Email	Arseny.Shur@usu.ru
Number-of-Cited-References	20
Journal-ISO	Theor. Comput. Syst.
Doc-Delivery-Number	AA3KV