Edita Pelantová ; Štěpán Starosta - Constructions of words rich in palindromes and pseudopalindromes

dmtcs:655 - Discrete Mathematics & Theoretical Computer Science, November 22, 2016, Vol. 18 no. 3 - https://doi.org/10.46298/dmtcs.655
Constructions of words rich in palindromes and pseudopalindromes

Authors: Edita Pelantová ; Štěpán Starosta

A narrow connection between infinite binary words rich in classical palindromes and infinite binary words rich simultaneously in palindromes and pseudopalindromes (the so-called $H$-rich words) is demonstrated. The correspondence between rich and $H$-rich words is based on the operation $S$ acting over words over the alphabet $\{0,1\}$ and defined by $S(u_0u_1u_2\ldots) = v_1v_2v_3\ldots$, where $v_i= u_{i-1} + u_i \mod 2$. The operation $S$ enables us to construct a new class of rich words and a new class of $H$-rich words. Finally, the operation $S$ is considered on the multiliteral alphabet $\mathbb{Z}_m$ as well and applied to the generalized Thue--Morse words. As a byproduct, new binary rich and $H$-rich words are obtained by application of $S$ on the generalized Thue--Morse words over the alphabet $\mathbb{Z}_4$.

Volume: Vol. 18 no. 3
Section: Combinatorics
Published on: November 22, 2016
Accepted on: November 22, 2016
Submitted on: November 9, 2016
Keywords: Mathematics - Combinatorics,68R15


Consultation statistics

This page has been seen 431 times.
This article's PDF has been downloaded 254 times.