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 pseudopalindromesArticle

Authors: Edita Pelantová ORCID; Š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: October 18, 2016
    Submitted on: November 9, 2016
    Keywords: Mathematics - Combinatorics,68R15

    1 Document citing this article

    Consultation statistics

    This page has been seen 729 times.
    This article's PDF has been downloaded 421 times.