Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

Request Permissions   Purchase Content 
 
 

 

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?)

  • [1] Arturo Carpi, On abelian power-free morphisms, Internat. J. Algebra Comput. 3 (1993), no. 2, 151-167. MR 1233218 (94g:68087), https://doi.org/10.1142/S0218196793000123
  • [2] Arturo Carpi, On the number of abelian square-free words on four letters, Discrete Appl. Math. 81 (1998), no. 1-3, 155-167. MR 1492008 (98j:68139), https://doi.org/10.1016/S0166-218X(97)88002-X
  • [3] F. M. Dekking, Strongly nonrepetitive sequences and progression-free sets, J. Combin. Theory Ser. A 27 (1979), no. 2, 181-185. MR 542527 (81b:05027), https://doi.org/10.1016/0097-3165(79)90044-X
  • [4] R. C. Entringer, D. E. Jackson, and J. A. Schatz, On nonrepetitive sequences, J. Combinatorial Theory Ser. A 16 (1974), 159-164. MR 0332533 (48 #10860)
  • [5] Paul Erdős, Some unsolved problems, Michigan Math. J. 4 (1957), 291-300. MR 0098702 (20 #5157)
  • [6] Paul Erdős, Some unsolved problems, Magyar Tud. Akad. Mat. Kutató Int. Közl. 6 (1961), 221-254. MR 0177846 (31 #2106)
  • [7] A. A. Evdokimov, Strongly asymmetric sequences generated by a finite number of symbols., Dokl. Akad. Nauk SSSR 179 (1968), 1268-1271 (Russian). MR 0234842 (38 #3156)
  • [8] Aviezri S. Fraenkel and R. Jamie Simpson, How many squares must a binary sequence contain?, Electron. J. Combin. 2 (1995), Research Paper 2, approx. 9 pp. (electronic). MR 1309124 (96b:11023)
  • [9] Juhani Karhumaki, Aleksi Saarela, and Luca Q. Zamboni, On a generalization of Abelian equivalence and complexity of infinite words, J. Combin. Theory Ser. A 120 (2013), no. 8, 2189-2206. MR 3102181, https://doi.org/10.1016/j.jcta.2013.08.008
  • [10] Veikko Keränen, Abelian squares are avoidable on $ 4$ letters, Automata, Languages and Programming (Vienna, 1992) Lecture Notes in Comput. Sci., vol. 623, Springer, Berlin, 1992, pp. 41-52. MR 1250629 (94j:68244), https://doi.org/10.1007/3-540-55719-9_62
  • [11] Veikko Keränen, New abelian square-free DT0L-languages over 4 letters., Manuscript (2003).
  • [12] M. Lothaire, Combinatorics on Words, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1997. MR 1475463 (98g:68134)
  • [13] P. A. B. Pleasants, Non-repetitive sequences, Proc. Cambridge Philos. Soc. 68 (1970), 267-274. MR 0265173 (42 #85)
  • [14] Michaël Rao, On some generalizations of abelian power avoidability, Theoret. Comput. Sci. 601 (2015), 39-46. MR 3396334, https://doi.org/10.1016/j.tcs.2015.07.026
  • [15] A. Thue, Über die gegenseitige lage gleicher teile gewisser zeichenreihen., Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania 10 (1912), 1-67.

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