10.46298/fi-2022-7243
https://fi.episciences.org/7243
Dolce, Francesco
Francesco
Dolce
Pelantová, Edita
Edita
Pelantová
On morphisms preserving palindromic richness
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.
episciences.org
Computer Science - Formal Languages and Automata Theory
Computer Science - Discrete Mathematics
68R15
arXiv.org - Non-exclusive license to distribute
2022-02-24
2022-03-10
2022-03-10
eng
journal article
arXiv:2006.12207
10.48550/arXiv.2006.12207
1875-8681
https://fi.episciences.org/7243/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 185, Issue 1
Researchers
Students