Kybernetika 48 no. 3, 361-370, 2012

Generalized Thue-Morse words and palindromic richnes

Štěpán Starosta

Abstract:

We prove that the generalized Thue-Morse word $\mathbf{t}_{b,m}$ defined for $b \geq 2$ and $m \geq 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}$.

Keywords:

palindrome, palindromic richness, Thue-Morse, Theta-palindrome

Classification:

68R15

References:

  1. J.-P. Allouche and J. Shallit: Sums of digits, overlaps, and palindromes. Discrete Math. Theoret. Comput. Sci. 4 (2000), 1-10.   CrossRef
  2. P. Baláži, Z. Masáková and E. Pelantová: Factor versus palindromic complexity of uniformly recurrent infinite words. Theoret. Comput. Sci. 380 (2007), 3, 266-275.   CrossRef
  3. L. Balková: Factor frequencies in generalized Thue-Morse words. Kybernetika 48 (2012), 3, 371-385.   CrossRef
  4. S. Brlek: Enumeration of factors in the Thue-Morse word. Discrete Appl. Math. 24 (1989), 1-3, 83-96.   CrossRef
  5. S. Brlek, S. Hamel, M. Nivat and C. Reutenauer: On the palindromic complexity of infinite words. Internat. J. Found. Comput. 15 (2004), 2, 293-306.   CrossRef
  6. M. Bucci, A. {De Luca}, A. Glen and L. Q. Zamboni: A connection between palindromic and factor complexity using return words. Adv. Appl. Math. 42 (2009), no. 1, 60-74.   CrossRef
  7. J. Cassaigne: Complexity and special factors. Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 1, 67-88.   CrossRef
  8. A. de Luca and S. Varricchio: Some combinatorial properties of the Thue-Morse sequence and a problem in semigroups. Theoret. Comput. Sci. 63 (1989), 3, 333-348.   CrossRef
  9. X. Droubay, J. Justin and G. Pirillo: Episturmian words and some constructions of de Luca and Rauzy. Theoret. Comput. Sci. 255 (2001), 1-2, 539-553.   CrossRef
  10. A. Frid: Applying a uniform marked morphism to a word. Discrete Math. Theoret. Comput. Sci. 3 (1999), 125-140.   CrossRef
  11. A. Glen, J. Justin, S. Widmer and L. Q. Zamboni: Palindromic richness. European J. Combin. 30 (2009), 2, 510-531.   CrossRef
  12. E. Pelantová and Š. Starosta: Languages invariant under more symmetries: overlapping factors versus palindromic richness. To appear in Discrete Math., preprint available at \url{http://arxiv.org/abs/1103.4051} (2011).   CrossRef
  13. E. Prouhet: Mémoire sur quelques relations entre les puissances des nombres. C. R. Acad. Sci. Paris 33 (1851), 225.   CrossRef
  14. Š. Starosta: On theta-palindromic richness. Theoret. Comput. Sci. 412 (2011), 12-14, 1111-1121.   CrossRef
  15. J. Tromp and J. Shallit: Subword complexity of a generalized Thue-Morse word. Inf. Process. Lett. (1995), 313-316.   CrossRef