Factor versus palindromic complexity of uniformly recurrent infinite words

Result code in 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>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Factor versus palindromic complexity of uniformly recurrent infinite words

Original language description

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.

Czech name

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

Czech description

Studujeme vztah palindromické a faktorové komplexity nekonečných slov. Ukazujeme, že pro uniformně rekurentní slova platí $P(n)+P(n+1) leq Delta {mathcal C}(n) + 2,$ pro všechna $n inN$. Pro velkou třídu slov je toto lepší odhad palindromické komplexity pomocí faktorové komplexity, než ten, který byl prezentován v článku Allouche et al. Dáváme několik příkladů nekonečných slov, pro které se v našem odhadu nabývá horní mez. Speciálně odvozujeme explicitní předpis pro palindromickou komplexitu nekonečných slov kódujících výměnu $r$ intervalů. Jestliže permutace $pi$ spojená s transformací výměny intervalů je dána předpisem $pi(k)=r+1-k$ pro všechna $k$, pak existuje právě jeden palindrom každé sudé délky a právě $r$ palindromů každé liché délky.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

BA - General mathematics

OECD FORD branch

—

Project

<a href="/en/project/GA201%2F05%2F0169" target="_blank" >GA201/05/0169: Algebraic and combinatorial aspects of aperiodic structures</a><br>

Continuities

Z - Vyzkumny zamer (s odkazem do CEZ)

Publication year

2007

Confidentiality

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

Name of the periodical

Theoretical Computer Science

ISSN

0304-3975

e-ISSN

—

Volume of the periodical

2007

Issue of the periodical within the volume

380

Country of publishing house

GB - UNITED KINGDOM

Number of pages

10

Pages from-to

266-275

UT code for WoS article

—

EID of the result in the Scopus database

—