On abelian repetition threshold

Alexey V. Samsonov; Arseny M. Shur

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2012)

  • Volume: 46, Issue: 1, page 147-163
  • ISSN: 0988-3754

Abstract

top
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.

How to cite

top

Samsonov, Alexey V., and Shur, Arseny M.. "On abelian repetition threshold." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 46.1 (2012): 147-163. <http://eudml.org/doc/273053>.

@article{Samsonov2012,
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 = {Samsonov, Alexey V., Shur, Arseny M.},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {repetition threshold; formal languages; avoidable repetitions; abelian powers},
language = {eng},
number = {1},
pages = {147-163},
publisher = {EDP-Sciences},
title = {On abelian repetition threshold},
url = {http://eudml.org/doc/273053},
volume = {46},
year = {2012},
}

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
PB - EDP-Sciences
VL - 46
IS - 1
SP - 147
EP - 163
AB - 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.
LA - eng
KW - repetition threshold; formal languages; avoidable repetitions; abelian powers
UR - http://eudml.org/doc/273053
ER -

References

top
  1. [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). Zbl1101.68741MR2084859
  2. [2] F.-J. Brandenburg, Uniformly growing k-th power free homomorphisms. Theoret. Comput. Sci.23 (1983) 69–82. Zbl0508.68051MR693069
  3. [3] A. Carpi, On the number of Abelian square-free words on four letters. Discrete Appl. Math.81 (1998) 155–167. Zbl0894.68113MR1492008
  4. [4] A. Carpi, On Dejean’s conjecture over large alphabets. Theoret. Comput. Sci.385 (2007) 137–151. Zbl1124.68087MR2356248
  5. [5] M. Crochemore, F. Mignosi and A. Restivo, Automata and forbidden words. Inf. Process. Lett.67 (1998) 111–117. Zbl06590735MR1638178
  6. [6] J.D. Currie, The number of binary words avoiding Abelian fourth powers grows exponentially. Theoret. Comput. Sci.319 (2004) 441–446. Zbl1068.68113MR2074965
  7. [7] J.D. Currie and N. Rampersad, A proof of Dejean’s conjecture. Math. Comput.80 (2011) 1063–1070. Zbl1215.68192
  8. [8] F. Dejean, Sur un théorème de Thue. J. Comb. Th. (A) 13 (1972) 90–99. Zbl0245.20052MR300959
  9. [9] F.M. Dekking, Strongly non-repetitive sequences and progression-free sets. J. Comb. Th. (A) 27 (1979) 181–185. Zbl0437.05011MR542527
  10. [10] P. Erdös, Some unsolved problems. Magyar Tud. Akad. Mat. Kutató Int. Közl.6 (1961) 221–264. Zbl0100.02001MR177846
  11. [11] V. Keränen, Abelian squares are avoidable on 4 letters, in Proc. ICALP’92. Lect. Notes Comput. Sci. 623 (1992) 41–52. MR1250629
  12. [12] V. Keränen, A powerful abelian square-free substitution over 4 letters. Theoret. Comput. Sci.410 (2009) 3893–3900. Zbl1172.68035MR2553340
  13. [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. [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. Zbl1230.68163MR2830264
  15. [15] A.M. Shur, Comparing complexity functions of a language and its extendable part. RAIRO-Theor. Inf. Appl. 42 (2008) 647–655. Zbl1149.68055MR2434040
  16. [16] A. M. Shur, Growth rates of complexity of power-free languages. Theoret. Comput. Sci.411 (2010) 3209–3223. Zbl1196.68121MR2676864
  17. [17] A. Thue, Über unendliche Zeichenreihen. Kra. Vidensk. Selsk. Skrifter. I. Mat. Nat. Kl. Christiana7 (1906) 1–22. JFM37.0066.17

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.