Voir la notice de l'article provenant de la source Numdam
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.
@article{ITA_2012__46_1_147_0,
author = {Samsonov, Alexey V. and Shur, Arseny M.},
title = {On abelian repetition threshold},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {147--163},
publisher = {EDP-Sciences},
volume = {46},
number = {1},
year = {2012},
doi = {10.1051/ita/2011127},
mrnumber = {2904967},
zbl = {1279.68240},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.1051/ita/2011127/}
}
TY - JOUR AU - Samsonov, Alexey V. AU - Shur, Arseny M. TI - On abelian repetition threshold JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications PY - 2012 SP - 147 EP - 163 VL - 46 IS - 1 PB - EDP-Sciences UR - http://geodesic.mathdoc.fr/articles/10.1051/ita/2011127/ DO - 10.1051/ita/2011127 LA - en ID - ITA_2012__46_1_147_0 ER -
%0 Journal Article %A Samsonov, Alexey V. %A Shur, Arseny M. %T On abelian repetition threshold %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2012 %P 147-163 %V 46 %N 1 %I EDP-Sciences %U http://geodesic.mathdoc.fr/articles/10.1051/ita/2011127/ %R 10.1051/ita/2011127 %G en %F ITA_2012__46_1_147_0
Samsonov, Alexey V.; Shur, Arseny M. On abelian repetition threshold. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 147-163. doi: 10.1051/ita/2011127
Cité par Sources :