Combinatorics on words obtaining by \(k\) to \(k\) substitution and \(k\) to \(k\) exchange of a letter on modulo-recurrent words

Moussa BARRO; K. Ernest BOGNINI; Théodore TAPSOBA

doi:10.26637/mjm11S/006

Abstract

We introduce two new concepts which are the \(k\) to \(k\) substitution and \(k\) to \(k\) exchange of a letter on infinite words. After studying the return words and the special factors of words obtaining by these applications on Sturmian words and modulo-recurrent words. Next, we establish the complexity functions of these words. Finally, we determine the palindromic complexity of these words.

Keywords:

Sturmian words, modulo-recursive, complexity function, palindrome, \(k\) to \(k\) substitution, \(k\) to \(k\) exchange

Mathematics Subject Classification:

68R15, 11B85, 03D15

Authors Imprint References Funding Related Articles Downloads

Moussa BARRO Département de Mathématiques et Informatique, Université Nazi BONI,01 BP 1091 Bobo-Dioulasso 01, Burkina Faso. https://orcid.org/0009-0008-7748-2454
K. Ernest BOGNINI Centre Universitaire de Kaya (CU-K), Université Joseph KI-ZERBO, 03 BP 7021 Ouagadougou, Burkina Faso. https://orcid.org/0000-0002-6265-8065
Théodore TAPSOBA Département de Mathématiques et Informatique, Université Nazi BONI,01 BP 1091 Bobo-Dioulasso 01, Burkina Faso. https://orcid.org/0009-0005-7899-7079

Pages: 82-91
Date Published: 01-10-2023
Vol. 11 No. S (2023): Malaya Journal of Matematik (MJM): Special Issue Dedicated to Professor Gaston M. N'Guérékata’s 70th Birthday

J. P. A LLOUCHE , Sur la complexité des suites infinies, Bull. Belg. Math. Soc. Simon Stevin, 1(1994), 133– DOI: https://doi.org/10.36045/bbms/1103408543

J. P. A LLOUCHE , M. B AAKE , J. C ASSAIGNE AND D. D AMANIK , Palindrome complexity, Theoret. Comput.

Sci., 292(2003), 9–33. DOI: https://doi.org/10.1055/s-2003-44661

M. B ARRO , I. K ABOR ´ E , T. T APSOBA , About the words by k to k erasure of letter and the words of erased letters: Sturmian case, IJAM., 32(2)(2019), 189–204. DOI: https://doi.org/10.12732/ijam.v32i2.3

M. B ARRO , I. K ABOR ´ E , T. T APSOBA , On the words by k to k insertion of a letter in sturmian words, IJAM., 30(5)(2017), 387–400. DOI: https://doi.org/10.12732/ijam.v30i5.3

J. B ERSTEL , Sturmian and episturmian words (a survey of some recent resultats), Lect. Notes in Comput.

Sci., 4728(2007).

V. B ERTH ´ E , Fréquences des facteurs des suites sturmiennes, Theoret. Comput. Sci., 165(1996), 295–309. DOI: https://doi.org/10.1016/0304-3975(95)00224-3

J. C ASSAIGNE , Complexité et facteurs spéciaux, Bull. Belg. Math. Soc. Simon Stevin, 4(1997), 67–88. DOI: https://doi.org/10.36045/bbms/1105730624

J. C ASSAIGNE , I. K ABOR ´ E , T. T APSOBA , On a new notion of complexity on infinite words, Acta Univ.

Sapentiae, Mathematica, 2(2010), 127–136.

E. M. C OVEN , Sequences with minimal block growth, Math. Syst. Theory, 8(1975), 376–382. DOI: https://doi.org/10.1007/BF01780584

E. M. C OVEN , G. A. H EDLUND , Sequences with minimal block growth, Math. Syst. Theory,7(1971),138–153. DOI: https://doi.org/10.1007/BF01762232

X. D ROUBAY , G. P IRILLO , Palindromes and Sturmian words, Theoret. Comput. Sci., 223(1-2)(1999), 73–85. DOI: https://doi.org/10.1016/S0304-3975(97)00188-6

I. K ABOR ´ E , About k to k insertion words of sturmian words, IJPAM, 79(4)(2012), 561–572.

I. K ABOR ´ E , T. T APSOBA ,Combinatoire des mots récurrents de complexités n + 2, RAIRO-Theo. Inf. Appl., 41(2007), 425–446. DOI: https://doi.org/10.1051/ita:2007027

M. L OTHAIRE , Algebraic combinatorics on words, Cambridge University Press, 2002. DOI: https://doi.org/10.1017/CBO9781107326019