Constructions of words rich in palindromes and pseudopalindromes

Abstract

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_0{u}_1{u}_2\dots )=v_1{v}_2{v}_3\dots$, where $v_i=u_{i-1}+u_i\mathrm{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$.

26 pages

References in corpus (5)

• Aperiodic pseudorandom number generators based on infinite words
• Palindromic richness for languages invariant under more symmetries
• Proof of Brlek-Reutenauer conjecture
• Palindromic closures using multiple antimorphisms
• Morphic images of episturmian words having finite palindromic defect

Cited by in corpus (2)

• Repetitions in infinite palindrome-rich words
• On Words with the Zero Palindromic Defect