On Morphisms Preserving Palindromic Richness

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21240%2F22%3A00356431" target="_blank" >RIV/68407700:21240/22:00356431 - isvavai.cz</a>

Nalezeny alternativní kódy

RIV/68407700:21340/22:00356431

Výsledek na webu

<a href="https://doi.org/10.3233/FI-222102" target="_blank" >https://doi.org/10.3233/FI-222102</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.3233/FI-222102" target="_blank" >10.3233/FI-222102</a>

Jazyk výsledku

angličtina

Název v původním jazyce

On Morphisms Preserving Palindromic Richness

Popis výsledku v původním jazyce

Itisknownthateachwordoflengthncontainsatmostn+1distinctpalindromes.A finite rich word is a word with maximal number of palindromic factors. The definition of palin- dromic richness can be naturally extended to infinite words. Sturmian words and Rote comple- mentary 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 al- phabets. 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.

Název v anglickém jazyce

On Morphisms Preserving Palindromic Richness

Popis výsledku anglicky

Itisknownthateachwordoflengthncontainsatmostn+1distinctpalindromes.A finite rich word is a word with maximal number of palindromic factors. The definition of palin- dromic richness can be naturally extended to infinite words. Sturmian words and Rote comple- mentary 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 al- phabets. 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.

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.

Návaznosti

P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)

Rok uplatnění

2022

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název periodika

Fundamenta Informaticae

ISSN

0169-2968

e-ISSN

1875-8681

Svazek periodika

185

Číslo periodika v rámci svazku

1

Stát vydavatele periodika

NL - Nizozemsko

Počet stran výsledku

25

Strana od-do

1-25

Kód UT WoS článku

000772192700001

EID výsledku v databázi Scopus

2-s2.0-85127384414