Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
palindrome; palindromic richness; Thue-Morse; Theta-palindrome
palindrome; palindromic richness; Thue-Morse; Theta-palindrome
Summary:
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}$.
References:
[1] Allouche, J.-P., Shallit, J.: Sums of digits, overlaps, and palindromes. Discrete Math. Theoret. Comput. Sci. 4 (2000), 1–10. MR 1755723 | Zbl 1013.11004
[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 10.1016/j.tcs.2007.03.019 | MR 2330997 | Zbl 1119.68137
[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 10.1016/0166-218X(92)90274-E | MR 1011264 | Zbl 0683.20045
[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 10.1142/S012905410400242X | MR 2071459 | Zbl 1067.68113
[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 10.1016/j.aam.2008.03.005 | MR 2475313 | Zbl 1160.68027
[7] Cassaigne, J.: Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 1, 67–88. MR 1440670 | Zbl 0921.68065
[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 10.1016/0304-3975(89)90013-3 | MR 0993769 | Zbl 0671.10050
[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 10.1016/S0304-3975(99)00320-5 | MR 1819089 | Zbl 0981.68126
[10] Frid, A.: Applying a uniform marked morphism to a word. Discrete Math. Theoret. Comput. Sci. 3 (1999), 125–140. MR 1734902 | Zbl 0935.68055
[11] Glen, A., Justin, J., Widmer, S., Zamboni, L. Q.: Palindromic richness. European J. Combin. 30 (2009), 2, 510–531. DOI 10.1016/j.ejc.2008.04.006 | MR 2489283 | Zbl 1169.68040
[12] Pelantová, E., Starosta, Š.: Languages invariant under more symmetries: overlapping factors versus palindromic richness. To appear in Discrete Math., preprint available at http://arxiv.org/abs/1103.4051 (2011).
[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 10.1016/j.tcs.2010.12.011 | MR 2797753 | Zbl 1211.68302
[15] Tromp, J., Shallit, J.: Subword complexity of a generalized Thue-Morse word. Inf. Process. Lett. (1995), 313–316. DOI 10.1016/0020-0190(95)00074-M | MR 1336711 | Zbl 0875.68596
Search
Partner of
