On Morphisms Preserving Palindromic Richness

Article type: Research Article

Authors: Dolce, Francesco | Pelantová, Edita^{; *}

Affiliations: Czech Technical University in Prague, 160 00 Prague 6 - Dejvice, Czech Republic. [email protected], [email protected]

Correspondence: [*] Address for correspondence: Czech Technical University in Prague, 160 00 Prague 6 - Dejvice, Czech Republic.

Abstract: It is known that each word of length n contains at most n + 1 distinct palindromes. A finite rich word is a word with maximal number of palindromic factors. The definition of palindromic richness can be naturally extended to infinite words. Sturmian words and Rote complementary symmetric sequences form two classes of binary rich words, while episturmian words and words coding symmetric d-interval exchange transformations give us other examples on larger alphabets. In this paper we look for morphisms of the free monoid, which allow us to construct new rich words from already known rich words. We focus on morphisms in Class Pret. This class contains morphisms injective on the alphabet and satisfying a particular palindromicity property: for every morphism ϕ in the class there exists a palindrome w such that ϕ(a)w is a first complete return word to w for each letter a. We characterize Pret morphisms which preserve richness over a binary alphabet. We also study marked Pret morphisms acting on alphabets with more letters. In particular we show that every Arnoux-Rauzy morphism is conjugated to a morphism in Class Pret and that it preserves richness.

Keywords: Palindromic richness, morphisms, bispecial factors, Class P_ret, Class P

DOI: 10.3233/FI-222102

Journal: Fundamenta Informaticae, vol. 185, no. 1, pp. 1-25, 2022