Antisquares and Critical Exponents - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2023

Antisquares and Critical Exponents

Aseem Baranwal
  • Fonction : Auteur
  • PersonId : 1171991
James Currie
  • Fonction : Auteur
  • PersonId : 1171992
Lucas Mol
  • Fonction : Auteur
  • PersonId : 1171993
Pascal Ochem
Narad Rampersad
  • Fonction : Auteur
  • PersonId : 1171994
Jeffrey Shallit

Résumé

The complement $\bar{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. An antisquare is a nonempty word of the form $x\, \bar{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 large number. We say a binary word is 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 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.
Fichier principal
Vignette du fichier
2209.09223v3.pdf (462.82 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

lirmm-03799689 , version 1 (17-10-2023)
lirmm-03799689 , version 2 (23-07-2024)

Licence

Identifiants

Citer

Aseem Baranwal, James Currie, Lucas Mol, Pascal Ochem, Narad Rampersad, et al.. Antisquares and Critical Exponents. Discrete Mathematics and Theoretical Computer Science, 2023, 25 (2), pp.#11. ⟨10.46298/dmtcs.10063⟩. ⟨lirmm-03799689v2⟩
63 Consultations
31 Téléchargements

Altmetric

Partager

More