Generalized Thue-Morse words and palindromic richness

Štěpán Starosta

Kybernetika (2012)

  • Volume: 48, Issue: 3, page 361-370
  • ISSN: 0023-5954

Abstract

top
We prove that the generalized Thue-Morse word 𝐭 b , m defined for b ≥ 2 and m ≥ 1 as 𝐭 b , m = s b ( n ) mod m n = 0 + ∞ , 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 2 m consisting of morphisms and antimorphisms. Considering antimorphisms Θ ∈ D m , we show that 𝐭 b , m is saturated by Θ -palindromes up to the highest possible level. Using the generalisation of palindromic richness recently introduced by the author and E. Pelantová, we show that 𝐭 b , m is D m -rich. We also calculate the factor complexity of 𝐭 b , m .

How to cite

top

Starosta, Štěpán. "Generalized Thue-Morse words and palindromic richness." Kybernetika 48.3 (2012): 361-370. <http://eudml.org/doc/246604>.

@article{Starosta2012,
abstract = {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\}$.},
author = {Starosta, Štěpán},
journal = {Kybernetika},
keywords = {palindrome; palindromic richness; Thue-Morse; Theta-palindrome; palindrome; palindromic richness; Thue-Morse; Theta-palindrome},
language = {eng},
number = {3},
pages = {361-370},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Generalized Thue-Morse words and palindromic richness},
url = {http://eudml.org/doc/246604},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Starosta, Štěpán
TI - Generalized Thue-Morse words and palindromic richness
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 3
SP - 361
EP - 370
AB - 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}$.
LA - eng
KW - palindrome; palindromic richness; Thue-Morse; Theta-palindrome; palindrome; palindromic richness; Thue-Morse; Theta-palindrome
UR - http://eudml.org/doc/246604
ER -

References

top
  1. Allouche, J.-P., Shallit, J., Sums of digits, overlaps, and palindromes, Discrete Math. Theoret. Comput. Sci. 4 (2000), 1–10. Zbl1013.11004MR1755723
  2. Baláži, P., Masáková, Z., Pelantová, E., 10.1016/j.tcs.2007.03.019, Theoret. Comput. Sci. 380 (2007), 3, 266–275. Zbl1119.68137MR2330997DOI10.1016/j.tcs.2007.03.019
  3. Balková, L., Factor frequencies in generalized Thue-Morse words, Kybernetika 48 (2012), 3, 371–385. 
  4. Brlek, S., 10.1016/0166-218X(92)90274-E, Discrete Appl. Math. 24 (1989), 1–3, 83–96. Zbl0683.20045MR1011264DOI10.1016/0166-218X(92)90274-E
  5. Brlek, S., Hamel, S., Nivat, M., Reutenauer, C., 10.1142/S012905410400242X, Internat. J. Found. Comput. 15 (2004), 2, 293–306. Zbl1067.68113MR2071459DOI10.1142/S012905410400242X
  6. Bucci, M., De Luca, A., Glen, A., Zamboni, L. Q., 10.1016/j.aam.2008.03.005, Adv. Appl. Math. 42 (2009), no. 1, 60–74. Zbl1160.68027MR2475313DOI10.1016/j.aam.2008.03.005
  7. Cassaigne, J., Complexity and special factors, Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 1, 67–88. Zbl0921.68065MR1440670
  8. de Luca, A., Varricchio, S., 10.1016/0304-3975(89)90013-3, Theoret. Comput. Sci. 63 (1989), 3, 333–348. Zbl0671.10050MR0993769DOI10.1016/0304-3975(89)90013-3
  9. Droubay, X., Justin, J., Pirillo, G., 10.1016/S0304-3975(99)00320-5, Theoret. Comput. Sci. 255 (2001), 1–2, 539–553. Zbl0981.68126MR1819089DOI10.1016/S0304-3975(99)00320-5
  10. Frid, A., Applying a uniform marked morphism to a word, Discrete Math. Theoret. Comput. Sci. 3 (1999), 125–140. Zbl0935.68055MR1734902
  11. Glen, A., Justin, J., Widmer, S., Zamboni, L. Q., 10.1016/j.ejc.2008.04.006, European J. Combin. 30 (2009), 2, 510–531. Zbl1169.68040MR2489283DOI10.1016/j.ejc.2008.04.006
  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, Š., 10.1016/j.tcs.2010.12.011, Theoret. Comput. Sci. 412 (2011), 12–14, 1111–1121. Zbl1211.68302MR2797753DOI10.1016/j.tcs.2010.12.011
  15. Tromp, J., Shallit, J., 10.1016/0020-0190(95)00074-M, Inf. Process. Lett. (1995), 313–316. Zbl0875.68596MR1336711DOI10.1016/0020-0190(95)00074-M

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.