Geodesic
Antisquares and Critical Exponents
Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2.

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

The (bitwise) complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An $\textit{antisquare}$ is a nonempty word of the form $x\, \overline{x}$. In this paper, we study infinite binary words that do not contain arbitrarily large antisquares. For example, we show that the repetition threshold for the language of infinite binary words containing exactly two distinct antisquares is $(5+\sqrt{5})/2$. We also study repetition thresholds for related classes, where "two" in the previous sentence is replaced by a larger number. We say a binary word is $\textit{good}$ if the only antisquares it contains are $01$ and $10$. We characterize the minimal antisquares, that is, those words that are antisquares but all proper factors are good. We determine the growth rate of the number of good words of length $n$ and determine the repetition threshold between polynomial and exponential growth for the number of good words.
DOI : 10.46298/dmtcs.10063
Classification : 68Rxx 
@article{DMTCS_2024_25_2_a1,
     author = {Baranwal, Aseem and Currie, James and Mol, Lucas and Ochem, Pascal and Rampersad, Narad and Shallit, Jeffrey},
     title = {Antisquares and {Critical} {Exponents}},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {25},
     number = {2},
     year = {2023-2024},
     doi = {10.46298/dmtcs.10063},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10063/}
}
TY  - JOUR
AU  - Baranwal, Aseem
AU  - Currie, James
AU  - Mol, Lucas
AU  - Ochem, Pascal
AU  - Rampersad, Narad
AU  - Shallit, Jeffrey
TI  - Antisquares and Critical Exponents
JO  - Discrete mathematics & theoretical computer science
PY  - 2023-2024
VL  - 25
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10063/
DO  - 10.46298/dmtcs.10063
LA  - en
ID  - DMTCS_2024_25_2_a1
ER  - 
%0 Journal Article
%A Baranwal, Aseem
%A Currie, James
%A Mol, Lucas
%A Ochem, Pascal
%A Rampersad, Narad
%A Shallit, Jeffrey
%T Antisquares and Critical Exponents
%J Discrete mathematics & theoretical computer science
%D 2023-2024
%V 25
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10063/
%R 10.46298/dmtcs.10063
%G en
%F DMTCS_2024_25_2_a1
Baranwal, Aseem; Currie, James; Mol, Lucas; Ochem, Pascal; Rampersad, Narad; Shallit, Jeffrey. Antisquares and Critical Exponents. Discrete mathematics & theoretical computer science, Tome 25 (2023-2024) no. 2. doi : 10.46298/dmtcs.10063. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.10063/

Cité par Sources :