Geodesic
The repetition threshold for binary rich words
Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1

Voir la notice de l'article provenant de la source Episciences

A word of length $n$ is rich if it contains $n$ nonempty palindromic factors. An infinite word is rich if all of its finite factors are rich. Baranwal and Shallit produced an infinite binary rich word with critical exponent $2+\sqrt{2}/2$ ($\approx 2.707$) and conjectured that this was the least possible critical exponent for infinite binary rich words (i.e., that the repetition threshold for binary rich words is $2+\sqrt{2}/2$). In this article, we give a structure theorem for infinite binary rich words that avoid $14/5$-powers (i.e., repetitions with exponent at least 2.8). As a consequence, we deduce that the repetition threshold for binary rich words is $2+\sqrt{2}/2$, as conjectured by Baranwal and Shallit. This resolves an open problem of Vesti for the binary alphabet; the problem remains open for larger alphabets.
DOI : 10.23638/DMTCS-22-1-6
Classification : 68R15 
@article{DMTCS_2020_22_1_a4,
     author = {Currie, James D. and Mol, Lucas and Rampersad, Narad},
     title = {The repetition threshold for binary rich words},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {22},
     number = {1},
     year = {2020-2021},
     doi = {10.23638/DMTCS-22-1-6},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-6/}
}
TY  - JOUR
AU  - Currie, James D.
AU  - Mol, Lucas
AU  - Rampersad, Narad
TI  - The repetition threshold for binary rich words
JO  - Discrete mathematics & theoretical computer science
PY  - 2020-2021
VL  - 22
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-6/
DO  - 10.23638/DMTCS-22-1-6
LA  - en
ID  - DMTCS_2020_22_1_a4
ER  - 
%0 Journal Article
%A Currie, James D.
%A Mol, Lucas
%A Rampersad, Narad
%T The repetition threshold for binary rich words
%J Discrete mathematics & theoretical computer science
%D 2020-2021
%V 22
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.23638/DMTCS-22-1-6/
%R 10.23638/DMTCS-22-1-6
%G en
%F DMTCS_2020_22_1_a4
Currie, James D.; Mol, Lucas; Rampersad, Narad. The repetition threshold for binary rich words. Discrete mathematics & theoretical computer science, Tome 22 (2020-2021) no. 1. doi: 10.23638/DMTCS-22-1-6

Cité par Sources :