On abelian repetition threshold
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 46 (2012) no. 1, pp. 147-163.

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.

DOI : https://doi.org/10.1051/ita/2011127
Classification : 68Q70,  68R15
Mots clés : repetition threshold, formal languages, avoidable repetitions, abelian powers
@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},
zbl = {1279.68240},
mrnumber = {2904967},
language = {en},
url = {http://www.numdam.org/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
DA  - 2012///
SP  - 147
EP  - 163
VL  - 46
IS  - 1
PB  - EDP-Sciences
UR  - http://www.numdam.org/articles/10.1051/ita/2011127/
UR  - https://zbmath.org/?q=an%3A1279.68240
UR  - https://www.ams.org/mathscinet-getitem?mr=2904967
UR  - https://doi.org/10.1051/ita/2011127
DO  - 10.1051/ita/2011127
LA  - en
ID  - ITA_2012__46_1_147_0
ER  - 
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. http://www.numdam.org/articles/10.1051/ita/2011127/

[1] A. Aberkane, J.D. Currie and N. Rampersad, The number of ternary words avoiding Abelian cubes grows exponentially. J. Integer Seq. 7 (2004) 13 (electronic only). | MR 2084859 | Zbl 1101.68741

[2] F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci. 23 (1983) 69-82. | MR 693069 | Zbl 0508.68051

[3] A. Carpi, On the number of Abelian square-free words on four letters. Discrete Appl. Math. 81 (1998) 155-167. | MR 1492008 | Zbl 0894.68113

[4] A. Carpi, On Dejean's conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137-151. | MR 2356248 | Zbl 1124.68087

[5] M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inf. Process. Lett. 67 (1998) 111-117. | MR 1638178

[6] J.D. Currie, The number of binary words avoiding Abelian fourth powers grows exponentially. Theoret. Comput. Sci. 319 (2004) 441-446. | MR 2074965 | Zbl 1068.68113

[7] J.D. Currie and N. Rampersad, A proof of Dejean's conjecture. Math. Comput. 80 (2011) 1063-1070. | Zbl 1215.68192

[8] F. Dejean, Sur un théorème de Thue. J. Comb. Th. (A) 13 (1972) 90-99. | MR 300959 | Zbl 0245.20052

[9] F.M. Dekking, Strongly non-repetitive sequences and progression-free sets. J. Comb. Th. (A) 27 (1979) 181-185. | MR 542527 | Zbl 0437.05011

[10] P. Erdös, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961) 221-264. | MR 177846 | Zbl 0100.02001

[11] V. Keränen, Abelian squares are avoidable on 4 letters, in Proc. ICALP'92. Lect. Notes Comput. Sci. 623 (1992) 41-52. | MR 1250629

[12] V. Keränen, A powerful abelian square-free substitution over 4 letters. Theoret. Comput. Sci. 410 (2009) 3893-3900. | MR 2553340 | Zbl 1172.68035

[13] V. Keränen, Combinatorics on words - suppression of unfavorable factors in pattern avoidance. TMJ 11 (2010). Available at http://www.mathematica-journal.com/issue/v11i3/Keranen.html consulted in November 2011.

[14] M. Rao, Last cases of Dejean's conjecture. Theoret. Comput. Sci. 412 (2011) 3010-3018; Combinatorics on Words (WORDS 2009), 7th International Conference on Words. | MR 2830264 | Zbl 1230.68163

[15] A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl. 42 (2008) 647-655. | Numdam | MR 2434040 | Zbl 1149.68055

[16] A. M. Shur, Growth rates of complexity of power-free languages. Theoret. Comput. Sci. 411 (2010) 3209-3223. | MR 2676864 | Zbl 1196.68121

[17] A. Thue, Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. Christiana 7 (1906) 1-22. | JFM 37.0066.17

Cité par Sources :