ON ABELIAN REPETITION THRESHOLD / Samsonov Alexey V.,Shur Arseny M. // RAIRO-THEORETICAL INFORMATICS AND APPLICATIONS. - 2012. - V. 46, l. 1, SI. - P. 147-163.

ISSN/EISSN:

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

Type:

Article

Abstract:

We study the avoidance of Abelian powers of words and consider three reasonable generalizations of the notion of Abelian power to fractional powers. Our main goal is to find an Abelian analogue of the repetition threshold, i.e., a numerical value separating k-avoidable and k-unavoidable Abelian powers for each size k of the alphabet. We prove lower bounds for the Abelian repetition threshold for large alphabets and all definitions of Abelian fractional power. We develop a method estimating the exponential growth rate of Abelian-power-free languages. Using this method, we get non-trivial lower bounds for Abelian repetition threshold for small alphabets. We suggest that some of the obtained bounds are the exact values of Abelian repetition threshold. In addition, we provide upper bounds for the growth rates of some particular Abelian-power-free languages.

Author keywords:

Repetition threshold; formal languages; avoidable repetitions; Abelian powers DEJEANS CONJECTURE; WORDS; NUMBER

DOI:

10.1051/ita/2011127

Web of Science ID:

ISI:000301345900012

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

Другие поля

Поле	Значение
Month	JAN
Publisher	CAMBRIDGE UNIV PRESS
Address	32 AVENUE OF THE AMERICAS, NEW YORK, NY 10013-2473 USA
Language	English
Keywords-Plus	DEJEANS CONJECTURE; WORDS; NUMBER
Research-Areas	Computer Science
Web-of-Science-Categories	Computer Science, Information Systems
Author-Email	vonosmas@gmail.com Arseny.Shur@usu.ru
Number-of-Cited-References	18
Usage-Count-Last-180-days	2
Usage-Count-Since-2013	9
Journal-ISO	Rairo-Theor. Inform. Appl.
Doc-Delivery-Number	906LE