ON PANSIOT WORDS AVOIDING 3-REPETITIONS / Gorbunova Irina A.,Shur Arseny M. // INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE. - 2012. - V. 23, l. 8, SI. - P. 1583-1594.

ISSN/EISSN:

0129-0541 / нет данных

Type:

Article

Abstract:

The recently confirm Dejean's conjecture between the threshold between avoidable and unavoidable powers of words gave rise to interesting and challenging problems on the structure and growth of threshold words. Over any finite alphabet with k >= 5 letters, Pansiot words avoiding 3-repetitions form a regular language, which is a rather small supereet of the set of all threshold words. Using cylindric and 2-dimensional words, we prove that, as k approaches infinity, the growth rates of complexity for these regular languages tend to the growth rate of complexity of some ternary 2-dimensional language. The numerical estimate of this growth rate is approximate to 1.2421.

Author keywords:

Dejean's conjecture; threshold languages; Pansiot words; cylindric words; 2-dimensional words; combinatorial complexity DEJEANS CONJECTURE; COMPLEXITY

DOI:

10.1142/S0129054112400631

Web of Science ID:

ISI:000316500200002

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

—

Другие поля

Поле	Значение
Month	DEC
Publisher	WORLD SCIENTIFIC PUBL CO PTE LTD
Address	5 TOH TUCK LINK, SINGAPORE 596224, SINGAPORE
Language	English
Keywords-Plus	DEJEANS CONJECTURE; COMPLEXITY
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Theory \& Methods
Author-Email	i.a.gorbunova@gmail.com arseny.shur@usu.ru
Number-of-Cited-References	15
Usage-Count-Since-2013	1
Journal-ISO	Int. J. Found. Comput. Sci.
Doc-Delivery-Number	111EA