On 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%2F11%3A00183922" target="_blank" >RIV/68407700:21340/11:00183922 - isvavai.cz</a>
Nalezeny alternativní kódy
RIV/68407700:21240/11:00183922
Výsledek na webu
<a href="http://dx.doi.org/10.1016/j.tcs.2011.06.031" target="_blank" >http://dx.doi.org/10.1016/j.tcs.2011.06.031</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2011.06.031" target="_blank" >10.1016/j.tcs.2011.06.031</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On 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) = Sigma(+infinity)(n=0) 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 + 1) -P(u)(n), where C(u) and P(u) are the factor and palindromic complexity of u, respectively. BrIek and Reutenauer verified their conjecture for periodic infinite words. Using their result, we prove the conjecture for uniformly recurrent words. Moreover, we summarize results and some open problems related to defects, which may be useful for the proof of the Brlek-Reutenauer conjecture in full generality.
Název v anglickém jazyce
On 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) = Sigma(+infinity)(n=0) 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 + 1) -P(u)(n), where C(u) and P(u) are the factor and palindromic complexity of u, respectively. BrIek and Reutenauer verified their conjecture for periodic infinite words. Using their result, we prove the conjecture for uniformly recurrent words. Moreover, we summarize results and some open problems related to defects, which may be useful for the proof of the Brlek-Reutenauer conjecture in full generality.
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
Výsledek vznikl pri realizaci vícero projektů. Více informací v záložce Projekty.
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>Z - Vyzkumny zamer (s odkazem do CEZ)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2011
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
412
Číslo periodika v rámci svazku
41
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
7
Strana od-do
5649-5655
Kód UT WoS článku
000295498100001
EID výsledku v databázi Scopus
—