eng
episciences.org
Fundamenta Informaticae
0169-2968
1875-8681
2022-03-10
Volume 185, Issue 1
10.46298/fi-2022-7243
7243
journal article
On morphisms preserving palindromic richness
Francesco Dolce
Edita Pelantová
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 $P_{ret}$. This class contains morphisms injective on the
alphabet and satisfying a particular palindromicity property: for every
morphism $\varphi$ in the class there exists a palindrome $w$ such that
$\varphi(a)w$ is a first complete return word to $w$ for each letter $a$. We
characterize $P_{ret}$ morphisms which preserve richness over a binary
alphabet. We also study marked $P_{ret}$ morphisms acting on alphabets with
more letters. In particular we show that every Arnoux-Rauzy morphism is
conjugated to a morphism in Class $P_{ret}$ and that it preserves richness.
https://fi.episciences.org/7243/pdf
Computer Science - Formal Languages and Automata Theory
Computer Science - Discrete Mathematics
68R15