Upper bound for palindromic and factor complexity of rich words

Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F21%3A00347627" target="_blank" >RIV/68407700:21340/21:00347627 - isvavai.cz</a>
Result on the web
<a href="https://doi.org/10.1051/ita/2020008" target="_blank" >https://doi.org/10.1051/ita/2020008</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1051/ita/2020008" target="_blank" >10.1051/ita/2020008</a>

Result language
angličtina
Original language name
Upper bound for palindromic and factor complexity of rich words
Original language description
A finite word $w$ of length $n$ contains at most $n+1$ distinct palindromic factors. If the bound $n+1$ is attained, the word $w$ is called rich. An infinite word $w$ is called rich if every finite factor of $w$ is rich. Let $w$ be a word (finite or infinite) over an alphabet with $q>1$ letters, let $fac_w(n)$ be the set of factors of length $n$ of the word $w$, and let $pf_w(n)subseteq fac_w(n)$ be the set of palindromic factors of length $n$ of the word $w$. We present several upper bounds for $vert fac_w(n)vert$ and $vert pf_w(n)vert$, where $w$ is a rich word. Let $delta=frac{3}{2(ln{3}-ln{2})}$. In particular we show that [vert fac_w(n)vert leq (4q^{2}n)^{deltaln{2n}+2}mbox{.}] In 2007, Bal{'a}{v z}i, Mas{'a}kov{'a}, and Pelantov{'a} showed that [vert pf_w(n)vert +vert pf_w(n+1)vert leq vert fac_w(n+1)vert-vert fac_w(n)vert+2mbox{,}] where $w$ is an infinite word whose set of factors is closed under reversal. We prove this inequality for every finite word $v$ with $vert vvertgeq n+1$ and $fac_v(n+1)$ closed under reversal.
Czech name
—
Czech description
—

Type
J<sub>imp</sub> - Article in a specialist periodical, which is included in the Web of Science database
CEP classification
—
OECD FORD branch
10101 - Pure mathematics

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

Similar results(10)