Faktorová vs. palindromická komplexita uniformně rekurentních nekonečných slov

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F07%3A04137457" target="_blank" >RIV/68407700:21340/07:04137457 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Factor versus palindromic complexity of uniformly recurrent infinite words

Popis výsledku v původním jazyce

We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has $P(n)+P(n+1) leq Delta {mathcal C}(n) + 2,$ for all $n inN$. For a large class of words it is a better estimate of the palindromic complexity in terms of the factor complexity then the one presented in cite{AllBaaCasDam}. We provide several examples of infinite words for which our estimate reaches its upper bound. In particular, we derive an explicit prescription for the palindromic complexity of infinite words coding $r$-interval exchange transformations. If the permutation $pi$ connected with the transformation is given by $pi(k)=r+1-k$ for all $k$, then there is exactly one palindrome of every even length, and exactly $r$ palindromes of every odd length.

Název v anglickém jazyce

Factor versus palindromic complexity of uniformly recurrent infinite words

Popis výsledku anglicky

We study the relation between the palindromic and factor complexity of infinite words. We show that for uniformly recurrent words one has $P(n)+P(n+1) leq Delta {mathcal C}(n) + 2,$ for all $n inN$. For a large class of words it is a better estimate of the palindromic complexity in terms of the factor complexity then the one presented in cite{AllBaaCasDam}. We provide several examples of infinite words for which our estimate reaches its upper bound. In particular, we derive an explicit prescription for the palindromic complexity of infinite words coding $r$-interval exchange transformations. If the permutation $pi$ connected with the transformation is given by $pi(k)=r+1-k$ for all $k$, then there is exactly one palindrome of every even length, and exactly $r$ palindromes of every odd length.

Druh

J_x - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)

CEP obor

BA - Obecná matematika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F05%2F0169" target="_blank" >GA201/05/0169: Algebraické a kombinatorické aspekty aperiodických struktur</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

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

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Svazek periodika

2007

Číslo periodika v rámci svazku

380

Stát vydavatele periodika

GB - Spojené království Velké Británie a Severního Irska

Počet stran výsledku

10

Strana od-do

266-275

Kód UT WoS článku

—

EID výsledku v databázi Scopus

—