< Contents IJAM: Volume 30, No. 5 (2017)
ON THE WORDS BY k TO k INSERTION OF A LETTER
IN STURMIAN WORDS
Moussa Barro1, Idrissa Kaboré2, Théodore Tapsoba3
1,2,3Departement of Mathematics and Informatics
Université Nazi Boni
Bobo-Dioulasso, 01 BP 1091, BURKINA FASO

Abstract

We study the classical complexity of $k$ to $k$ insertion words of a letter in Sturmian words. Then, we determine the Abelian complexity and palindromic complexity of these words. Finally, we show that the $k$ to $k$ insertion of a letter $x$ in Sturmian words preserves the palindromic richness of Sturmian words if and only if $k = 1$.

Citation details of the article



Journal: International Journal of Applied Mathematics
Journal ISSN (Print): ISSN 1311-1728
Journal ISSN (Electronic): ISSN 1314-8060
Volume: 30
Issue: 5
Year: 2017

DOI: 10.12732/ijam.v30i5.3

Download Section



Download the full text of article from here.

You will need Adobe Acrobat reader. For more information and free download of the reader, please follow this link.

References

  1. [1] J.-P. Allouche, Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin, 1 (1994), 133-143.
  2. [2] J.-P. Allouche, M. Baake, J. Cassaigne, D. Damanik, Palindrome complexity, Theoret. Comput. Sci., 292 (2003), 9-31.
  3. [3] J. Berstel, Sturmian and episturmian words (a survery of some recent results), In: Proceedings of CAI 2007, Vol. 4728 of Lecture Notes in Computer Science, Springer-Verlag (2007).
  4. [4] V. Berthée, Fréquences des facteurs des suites sturmiennes, Theoret. Comput. Sci., 165 (1996), 295-309.
  5. [5] M. Bucci, A. De Luca, A. Glen, L.Q. Zamboni, A connection between palindromic and factor complexity using retun words, Adv. Appl. Math., 42, No 1 (2009), 60-74.
  6. [6] J. Cassaigne, Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin, 4 (1997), 67-88.
  7. [7] J. Cassaigne, I. Kaboré, T. Tapsoba, On a new notion of complexity on infinite words, Acta Univ. Sapentiae, Mathematica, 2 (2010), 127-136.
  8. [8] E.M. Coven, G.A. Hedlund, Sequences with minimal block growth, Math. Syst. Theory, 7 (1973), 138-153.
  9. [9] X. Droubay, G. Pirillo, Palindromes and Sturmian words, Theoret. Comput. Sci., 223, No 1-2 (1999), 73-85.
  10. [10] S. Dulucq, D. Gouyou-Beauchamps, Sur les facteurs des suites de Sturm, Theoret. Comput. Sci., 71 (1990), 381-400.
  11. [11] A. Glen, J. Justin, Episturmian words: A survery, RAIRO-Theo. Inf. Appl., 43 (2009), 402-433.
  12. [12] I. Kaboré, About k to k insertion words of Sturmian words, Intern. J. Pure Appl. Math., 79 No 4 (2012), 561-572.
  13. [13] I. Kaboré, T. Tapsoba, Combinatoire des mots récurrents de complexité n + 2, RAIRO-Theo. Inf. Appl., 41 (2007), 425-446.
  14. [14] M. Lothaire, Algebraic Combinatorics on Words, Cambridge University Press (2002).
  15. [15] F. Mignosi, P. Sébold, Morphismes sturmiens et règles de Rauzy, J. Théor. Nombres Bordeaux, 5 (1993), 221-233.