Complement Avoidance in Binary Words
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.
Authors
- Pascal Ochem (ORCID: https://orcid.org/0000-0001-5504-4586)
- Narad Rampersad (ORCID: https://orcid.org/0000-0001-7489-0980)
- Ľubomíra Dvořáková (ORCID: https://orcid.org/0000-0001-7208-4248)
- Daniela Opočenská
- Jeffrey Shallit (ORCID: https://orcid.org/0000-0003-1197-3820)
- James D. Currie (ORCID: https://orcid.org/0000-0002-0061-3849)
Institutions
- Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
- Czech Technical University in Prague (CZ)
- The University of Winnipeg (CA)
Publication Details
- Journal
- The Electronic Journal of Combinatorics
- Published
- 2025-10-17
- DOI
- https://doi.org/10.37236/11555
- Citations
- 1
- Primary Topic
- Natural Language Processing Techniques
- Type
- article
- Field-Weighted Citation Impact
- 2.48