Proof of the Brlek-Reutenauer conjecture
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F13%3A00201614" target="_blank" >RIV/68407700:21340/13:00201614 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/13:00201614
Výsledek na webu
<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.024" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2012.12.024</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2012.12.024" target="_blank" >10.1016/j.tcs.2012.12.024</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
Proof of the Brlek-Reutenauer conjecture
Popis výsledku v původním jazyce
Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u)= sum_{n=0}^{+infty}T_u(n) in which D(u) denotes the defect of u and T_u(n) denotes C_u(n+1)-C_u(n)+2 - P_u(n)-P_u(n+1), where C_u(n) and P_u(n) are the factor and palindromic complexity of u, respectively. This conjecture was verified for periodic words by Brlek and Reutenauer themselves. Using their results for periodic words, we have recently proved the conjecture for uniformly recurrent words. In the present article we prove the conjecture in its general version by a new method without exploiting the result for periodic words.
Název v anglickém jazyce
Proof of the Brlek-Reutenauer conjecture
Popis výsledku anglicky
Brlek and Reutenauer conjectured that any infinite word u with language closed under reversal satisfies the equality 2D(u)= sum_{n=0}^{+infty}T_u(n) in which D(u) denotes the defect of u and T_u(n) denotes C_u(n+1)-C_u(n)+2 - P_u(n)-P_u(n+1), where C_u(n) and P_u(n) are the factor and palindromic complexity of u, respectively. This conjecture was verified for periodic words by Brlek and Reutenauer themselves. Using their results for periodic words, we have recently proved the conjecture for uniformly recurrent words. In the present article we prove the conjecture in its general version by a new method without exploiting the result for periodic words.
Klasifikace
Druh
J<sub>x</sub> - Nezařazeno - Článek v odborném periodiku (Jimp, Jsc a Jost)
CEP obor
BA - Obecná matematika
OECD FORD obor
—
Návaznosti výsledku
Projekt
<a href="/cs/project/GA201%2F09%2F0584" target="_blank" >GA201/09/0584: Algebraické a kombinatorické aspekty aperiodických struktur</a><br>
Návaznosti
Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2013
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ů
Údaje specifické pro druh výsledku
Název periodika
Theoretical Computer Science
ISSN
0304-3975
e-ISSN
—
Svazek periodika
475
Číslo periodika v rámci svazku
—
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
6
Strana od-do
120-125
Kód UT WoS článku
000315309600013
EID výsledku v databázi Scopus
—