Upper bound for palindromic and factor complexity of rich words

Kód výsledku v 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>

Výsledek na webu

<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>

Jazyk výsledku

angličtina

Název v původním jazyce

Upper bound for palindromic and factor complexity of rich words

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Upper bound for palindromic and factor complexity of rich words

Popis výsledku anglicky

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.

Druh

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

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2021

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

RAIRO - Theoretical Informatics and Applications

ISSN

0988-3754

e-ISSN

1290-385X

Svazek periodika

2021

Číslo periodika v rámci svazku

55

Stát vydavatele periodika

FR - Francouzská republika

Počet stran výsledku

15

Strana od-do

—

Kód UT WoS článku

000609008300001

EID výsledku v databázi Scopus

2-s2.0-85099791551