On minimal critical exponent of balanced sequences
Identifikátory výsledku
Kód výsledku v IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21340%2F22%3A00362043" target="_blank" >RIV/68407700:21340/22:00362043 - isvavai.cz</a>
Výsledek na webu
<a href="https://doi.org/10.1016/j.tcs.2022.04.021" target="_blank" >https://doi.org/10.1016/j.tcs.2022.04.021</a>
DOI - Digital Object Identifier
<a href="http://dx.doi.org/10.1016/j.tcs.2022.04.021" target="_blank" >10.1016/j.tcs.2022.04.021</a>
Alternativní jazyky
Jazyk výsledku
angličtina
Název v původním jazyce
On minimal critical exponent of balanced sequences
Popis výsledku v původním jazyce
We study the threshold between avoidable and unavoidable repetitions in infinite balanced sequences over finite alphabets. The conjecture stated by Rampersad, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the alphabet of size d>4 equals (d-2)/(d-3). This conjecture is known to hold for d in {5, 6, 7,8,9,10}. We refute this conjecture by showing that the picture is different for bigger alphabets. We prove that critical exponents of balanced sequences over an alphabet of size d>10 are lower bounded by (d-1)/(d-2) and this bound is attained for all even numbers d>11. According to this result, we conjecture that the least critical exponent of a balanced sequence over d letters is (d-1)/(d-2) for all d>10.
Název v anglickém jazyce
On minimal critical exponent of balanced sequences
Popis výsledku anglicky
We study the threshold between avoidable and unavoidable repetitions in infinite balanced sequences over finite alphabets. The conjecture stated by Rampersad, Shallit and Vandomme says that the minimal critical exponent of balanced sequences over the alphabet of size d>4 equals (d-2)/(d-3). This conjecture is known to hold for d in {5, 6, 7,8,9,10}. We refute this conjecture by showing that the picture is different for bigger alphabets. We prove that critical exponents of balanced sequences over an alphabet of size d>10 are lower bounded by (d-1)/(d-2) and this bound is attained for all even numbers d>11. According to this result, we conjecture that the least critical exponent of a balanced sequence over d letters is (d-1)/(d-2) for all d>10.
Klasifikace
Druh
J<sub>imp</sub> - Článek v periodiku v databázi Web of Science
CEP obor
—
OECD FORD obor
10101 - Pure mathematics
Návaznosti výsledku
Projekt
<a href="/cs/project/EF16_019%2F0000778" target="_blank" >EF16_019/0000778: Centrum pokročilých aplikovaných přírodních věd</a><br>
Návaznosti
P - Projekt vyzkumu a vyvoje financovany z verejnych zdroju (s odkazem do CEP)<br>S - Specificky vyzkum na vysokych skolach
Ostatní
Rok uplatnění
2022
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
1879-2294
Svazek periodika
922
Číslo periodika v rámci svazku
June
Stát vydavatele periodika
GB - Spojené království Velké Británie a Severního Irska
Počet stran výsledku
12
Strana od-do
158-169
Kód UT WoS článku
000850360300013
EID výsledku v databázi Scopus
2-s2.0-85129523066