| Issue |
RAIRO-Theor. Inf. Appl.
Volume 46, Number 1, January-March 2012
Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique"
|
|
|---|---|---|
| Page(s) | 147 - 163 | |
| DOI | https://doi.org/10.1051/ita/2011127 | |
| Published online | 14 November 2011 | |
On Abelian repetition threshold
Institute of Mathematics and Computer Science, Ural Federal
University, 620083 pr. Lenina,
51
Ekaterinburg,
Russia
vonosmas@gmail.com; Arseny.Shur@usu.ru
Received:
2
November
2010
Accepted:
10
October
2011
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.
Mathematics Subject Classification: 68Q70 / 68R15
Key words: Repetition threshold / formal languages / avoidable repetitions / Abelian powers
© EDP Sciences 2011
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.