| Title:
|
Generalized Thue-Morse words and palindromic richness (English) |
| Author:
|
Starosta, Štěpán |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
48 |
| Issue:
|
3 |
| Year:
|
2012 |
| Pages:
|
361-370 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| 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}$. (English) |
| Keyword:
|
palindrome |
| Keyword:
|
palindromic richness |
| Keyword:
|
Thue-Morse |
| Keyword:
|
Theta-palindrome |
| MSC:
|
68R15 |
| idMR:
|
MR2975794 |
| . |
| Date available:
|
2012-08-31T15:46:54Z |
| Last updated:
|
2013-09-24 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/142943 |
| . |
| Reference:
|
[1] Allouche, J.-P., Shallit, J.: Sums of digits, overlaps, and palindromes.Discrete Math. Theoret. Comput. Sci. 4 (2000), 1–10. Zbl 1013.11004, MR 1755723 |
| Reference:
|
[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. Zbl 1119.68137, MR 2330997, 10.1016/j.tcs.2007.03.019 |
| Reference:
|
[3] Balková, L.: Factor frequencies in generalized Thue-Morse words.Kybernetika 48 (2012), 3, 371–385. |
| Reference:
|
[4] Brlek, S.: Enumeration of factors in the Thue-Morse word.Discrete Appl. Math. 24 (1989), 1–3, 83–96. Zbl 0683.20045, MR 1011264, 10.1016/0166-218X(92)90274-E |
| Reference:
|
[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. Zbl 1067.68113, MR 2071459, 10.1142/S012905410400242X |
| Reference:
|
[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. Zbl 1160.68027, MR 2475313, 10.1016/j.aam.2008.03.005 |
| Reference:
|
[7] Cassaigne, J.: Complexity and special factors.Bull. Belg. Math. Soc. Simon Stevin 4 (1997), 1, 67–88. Zbl 0921.68065, MR 1440670 |
| Reference:
|
[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. Zbl 0671.10050, MR 0993769, 10.1016/0304-3975(89)90013-3 |
| Reference:
|
[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. Zbl 0981.68126, MR 1819089, 10.1016/S0304-3975(99)00320-5 |
| Reference:
|
[10] Frid, A.: Applying a uniform marked morphism to a word.Discrete Math. Theoret. Comput. Sci. 3 (1999), 125–140. Zbl 0935.68055, MR 1734902 |
| Reference:
|
[11] Glen, A., Justin, J., Widmer, S., Zamboni, L. Q.: Palindromic richness.European J. Combin. 30 (2009), 2, 510–531. Zbl 1169.68040, MR 2489283, 10.1016/j.ejc.2008.04.006 |
| Reference:
|
[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). |
| Reference:
|
[13] Prouhet, E.: Mémoire sur quelques relations entre les puissances des nombres.C. R. Acad. Sci. Paris 33 (1851), 225. |
| Reference:
|
[14] Starosta, Š.: On theta-palindromic richness.Theoret. Comput. Sci. 412 (2011), 12–14, 1111–1121. Zbl 1211.68302, MR 2797753, 10.1016/j.tcs.2010.12.011 |
| Reference:
|
[15] Tromp, J., Shallit, J.: Subword complexity of a generalized Thue-Morse word.Inf. Process. Lett. (1995), 313–316. Zbl 0875.68596, MR 1336711, 10.1016/0020-0190(95)00074-M |
| . |
