Hostname: page-component-cd9895bd7-dk4vv Total loading time: 0 Render date: 2024-12-27T09:46:22.904Z Has data issue: false hasContentIssue false
  • English
  • Français

On Abelian repetition threshold

Published online by Cambridge University Press:  14 November 2011

Alexey V. Samsonov  and
Arseny M. Shur
Alexey V. Samsonov
Affiliation:
Institute of Mathematics and Computer Science, Ural Federal University, 620083 pr. Lenina, 51 Ekaterinburg, Russia. [email protected]; [email protected]
Arseny M. Shur
Affiliation:
Institute of Mathematics and Computer Science, Ural Federal University, 620083 pr. Lenina, 51 Ekaterinburg, Russia. [email protected]; [email protected]
Get access

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.

Keywords

Repetition thresholdformal languagesavoidable repetitionsAbelian powers
Type
Research Article
Information
RAIRO - Theoretical Informatics and Applications , Volume 46 , Issue 1: Special issue dedicated to the 13th "Journées Montoises d'Informatique Théorique" , January 2012 , pp. 147 - 163
Copyright
© EDP Sciences 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Références

Aberkane, A., Currie, J.D. and Rampersad, N., The number of ternary words avoiding Abelian cubes grows exponentially. J. Integer Seq. 7 (2004) 13 (electronic only). Google Scholar
Brandenburg, F.-J., Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci. 23 (1983) 69–82. Google Scholar
Carpi, A., On the number of Abelian square-free words on four letters. Discrete Appl. Math. 81 (1998) 155–167. Google Scholar
Carpi, A., On Dejean’s conjecture over large alphabets. Theoret. Comput. Sci. 385 (2007) 137–151. Google Scholar
Crochemore, M., Mignosi, F. and Restivo, A., Automata and forbidden words. Inf. Process. Lett. 67 (1998) 111–117. Google Scholar
Currie, J.D., The number of binary words avoiding Abelian fourth powers grows exponentially. Theoret. Comput. Sci. 319 (2004) 441–446. Google Scholar
Currie, J.D. and Rampersad, N., A proof of Dejean’s conjecture. Math. Comput. 80 (2011) 1063–1070. Google Scholar
Dejean, F., Sur un théorème de Thue. J. Comb. Th. (A) 13 (1972) 90–99. Google Scholar
Dekking, F.M., Strongly non-repetitive sequences and progression-free sets. J. Comb. Th. (A) 27 (1979) 181–185. Google Scholar
Erdös, P., Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961) 221–264. Google Scholar
Keränen, V., Abelian squares are avoidable on 4 letters, in Proc. ICALP’92. Lect. Notes Comput. Sci. 623 (1992) 41–52. Google Scholar
Keränen, V., A powerful abelian square-free substitution over 4 letters. Theoret. Comput. Sci. 410 (2009) 3893–3900. Google Scholar
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.
Rao, M., Last cases of Dejean’s conjecture. Theoret. Comput. Sci. 412 (2011) 3010–3018; Combinatorics on Words (WORDS 2009), 7th International Conference on Words. Google Scholar
Shur, A.M., Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl. 42 (2008) 647–655. Google Scholar
Shur, A. M., Growth rates of complexity of power-free languages. Theoret. Comput. Sci. 411 (2010) 3209–3223. Google Scholar
Thue, A., Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. Christiana 7 (1906) 1–22. Google Scholar