Complement Avoidance in Binary Words - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2023

Complement Avoidance in Binary Words

James Currie
  • Function : Author
  • PersonId : 1171992
Pascal Ochem
Narad Rampersad
  • Function : Author
  • PersonId : 1171994
Jeffrey Shallit


The complement $\overline{x}$ of a binary word $x$ is obtained by changing each $0$ in $x$ to $1$ and vice versa. We study infinite binary words $\bf w$ that avoid sufficiently large complementary factors; that is, if $x$ is a factor of $\bf w$ then $\overline{x}$ is not a factor of $\bf w$. In particular, we classify such words according to their critical exponents.
Fichier principal
Vignette du fichier
2209.09598.pdf (218.27 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-03799678 , version 1 (17-10-2023)





James Currie, Pascal Ochem, Narad Rampersad, Jeffrey Shallit. Complement Avoidance in Binary Words. 2023. ⟨lirmm-03799678⟩
12 View
6 Download



Gmail Facebook X LinkedIn More