Geodesic
Generalized Thue-Morse words and palindromic richness
Kybernetika, Tome 48 (2012) no. 3, pp. 361-370 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We prove that the generalized Thue-Morse word $\mathbf{t}_{b,m}$ defined for $b \ge 2$ and $m \ge 1$ as $\mathbf{t}_{b,m} = \left ( s_b(n) \mod m \right )_{n=0}^{+\infty}$, where $s_b(n)$ denotes the sum of digits in the base-$b$ representation of the integer $n$, has its language closed under all elements of a group $D_m$ isomorphic to the dihedral group of order $2m$ consisting of morphisms and antimorphisms. Considering antimorphisms $\Theta \in D_m$, we show that $\mathbf{t}_{b,m}$ is saturated by $\Theta$-palindromes up to the highest possible level. Using the generalisation of palindromic richness recently introduced by the author and E. Pelantová, we show that $\mathbf{t}_{b,m}$ is $D_m$-rich. We also calculate the factor complexity of $\mathbf{t}_{b,m}$.
We prove that the generalized Thue-Morse word $\mathbf{t}_{b,m}$ defined for $b \ge 2$ and $m \ge 1$ as $\mathbf{t}_{b,m} = \left ( s_b(n) \mod m \right )_{n=0}^{+\infty}$, where $s_b(n)$ denotes the sum of digits in the base-$b$ representation of the integer $n$, has its language closed under all elements of a group $D_m$ isomorphic to the dihedral group of order $2m$ consisting of morphisms and antimorphisms. Considering antimorphisms $\Theta \in D_m$, we show that $\mathbf{t}_{b,m}$ is saturated by $\Theta$-palindromes up to the highest possible level. Using the generalisation of palindromic richness recently introduced by the author and E. Pelantová, we show that $\mathbf{t}_{b,m}$ is $D_m$-rich. We also calculate the factor complexity of $\mathbf{t}_{b,m}$.
Classification : 68R15
Keywords: palindrome; palindromic richness; Thue-Morse; Theta-palindrome 
@article{KYB_2012_48_3_a1,
     author = {Starosta, \v{S}t\v{e}p\'an},
     title = {Generalized {Thue-Morse} words and palindromic richness},
     journal = {Kybernetika},
     pages = {361--370},
     year = {2012},
     volume = {48},
     number = {3},
     mrnumber = {2975794},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a1/}
}
TY  - JOUR
AU  - Starosta, Štěpán
TI  - Generalized Thue-Morse words and palindromic richness
JO  - Kybernetika
PY  - 2012
SP  - 361
EP  - 370
VL  - 48
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a1/
LA  - en
ID  - KYB_2012_48_3_a1
ER  - 
%0 Journal Article
%A Starosta, Štěpán
%T Generalized Thue-Morse words and palindromic richness
%J Kybernetika
%D 2012
%P 361-370
%V 48
%N 3
%U http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a1/
%G en
%F KYB_2012_48_3_a1
Starosta, Štěpán. Generalized Thue-Morse words and palindromic richness. Kybernetika, Tome 48 (2012) no. 3, pp. 361-370. http://geodesic.mathdoc.fr/item/KYB_2012_48_3_a1/

[1] Allouche, J.-P., Shallit, J.: Sums of digits, overlaps, and palindromes. Discrete Math. Theoret. Comput. Sci. 4 (2000), 1–10. | MR | Zbl

[2] Baláži, P., Masáková, Z., Pelantová, E.: Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007), 3, 266–275. | DOI | MR | Zbl

[3] Balková, L.: Factor frequencies in generalized Thue-Morse words. Kybernetika 48 (2012), 3, 371–385.

[4] Brlek, S.: Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989), 1–3, 83–96. | DOI | MR | Zbl

[5] Brlek, S., Hamel, S., Nivat, M., Reutenauer, C.: On the palindromic complexity of infinite words. Internat. J. Found. Comput. 15 (2004), 2, 293–306. | DOI | MR | Zbl

[6] Bucci, M., De Luca, A., Glen, A., Zamboni, L. Q.: A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009), no. 1, 60–74. | DOI | MR | Zbl

[7] Cassaigne, J.: Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 1, 67–88. | MR | Zbl

[8] de Luca, A., Varricchio, S.: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), 3, 333–348. | DOI | MR | Zbl

[9] Droubay, X., Justin, J., Pirillo, G.: Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001), 1–2, 539–553. | DOI | MR | Zbl

[10] Frid, A.: Applying a uniform marked morphism to a word. Discrete Math. Theoret. Comput. Sci. 3 (1999), 125–140. | MR | Zbl

[11] Glen, A., Justin, J., Widmer, S., Zamboni, L. Q.: Palindromic richness. European J. Combin. 30 (2009), 2, 510–531. | DOI | MR | Zbl

[12] Pelantová, E., Starosta, Š.: Languages invariant under more symmetries: overlapping factors versus palindromic richness. To appear in Discrete Math., preprint available at (2011). | arXiv

[13] Prouhet, E.: Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33 (1851), 225.

[14] Starosta, Š.: On theta-palindromic richness. Theoret. Comput. Sci. 412 (2011), 12–14, 1111–1121. | DOI | MR | Zbl

[15] Tromp, J., Shallit, J.: Subword complexity of a generalized Thue-Morse word. Inf. Process. Lett. (1995), 313–316. | DOI | MR | Zbl