A Unique Extension of Rich Words

DOI10.1016/J.TCS.2021.10.004MaRDI QIDQ6326383arXivFDO

Authors Josef Rukavicka

Publication date 2 October 2019

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.TCS.2021.10.004

Mathematics Subject Classification ID

Combinatorics on words (68R15)

arXiv classification

cs.DMmath.CO

Abstract: A word $w$ is called rich if it contains $|w|+1$ palindromic factors, including the empty word. We say that a rich word $w$ can be extended in at least two ways if there are two distinct letters $x,y$ such that $wx,wy$ are rich. Let $R$ denote the set of all rich words. Given $winR$, let $K(w)$ denote the set of all words such that if $uinK(w)$ then $wuinR$ and $wu$ can be extended in at least two ways. Let $omega(w)=min|u|miduinK(w)$ and let $phi(n)=maxomega(w)midwinRmboxand|w|=n$, where $n>0$. Vesti (2014) showed that $phi(n)leq2n$. In other words, it says that for each $winR$ there is a word $u$ with $|u|leq2|w|$ such that $wuinR$ and $wu$ can be extended in at least two ways. We prove that $phi(n)leqn$. In addition we prove that for each real constant $c>0$ and each integer $m>0$ there is $n>m$ such that $phi(n)geq(frac29-c)n$. The results hold for each finite alphabet having at least two letters.

This page was built for publication: A Unique Extension of Rich Words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6326383)