Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

Avoidability of long $ k$-abelian repetitions


Authors: Michaël Rao and Matthieu Rosenfeld
Journal: Math. Comp. 85 (2016), 3051-3060
MSC (2010): Primary 68R15
DOI: https://doi.org/10.1090/mcom/3085
Published electronically: February 18, 2016
MathSciNet review: 3522981
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We study the avoidability of long $ k$-abelian-squares and $ k$-abelian-cubes on binary and ternary alphabets. For $ k=1$, these are Mäkelä's questions. We show that one cannot avoid abelian-cubes of abelian period at least $ 2$ in infinite binary words, and therefore answering negatively one question from Mäkelä. Then we show that one can avoid $ 3$-abelian-squares of period at least $ 3$ in infinite binary words and $ 2$-abelian-squares of period at least 2 in infinite ternary words. Finally, we study the minimum number of distinct $ k$-abelian-squares that must appear in an infinite binary word.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 68R15

Retrieve articles in all journals with MSC (2010): 68R15


Additional Information

Michaël Rao
Affiliation: École Normale Supérieure de Lyon, LIP (UMR 5668 CNRS, ENSL, Inria, UCBL, UDL), 46 allée d’Italie, 69364 Lyon Cedex 07, France
Email: michael.rao@ens-lyon.fr

Matthieu Rosenfeld
Affiliation: École Normale Supérieure de Lyon, LIP (UMR 5668 CNRS, ENSL, Inria, UCBL, UDL), 46 allée d’Italie, 69364 Lyon Cedex 07, France
Email: matthieu.rosenfeld@ens-lyon.fr

DOI: https://doi.org/10.1090/mcom/3085
Received by editor(s): February 24, 2015
Received by editor(s) in revised form: May 29, 2015
Published electronically: February 18, 2016
Article copyright: © Copyright 2016 American Mathematical Society

American Mathematical Society