Half-Flips are 5-Avoidable
A word contains a half-flip if it contains non-empty factors [Formula: see text] and [Formula: see text] where [Formula: see text]. Fici reports a non-constructive proof of the existence of an infinite word over a finite alphabet avoiding half-flips and asks for the size of the smallest alphabet over which half-flips may be avoided. Currie and Rampersad have proposed a pure morphic word over 8 letters and a morphic word over 5 letters and conjecture that they avoid half-flips. We present a pure morphic word over 5 letters that avoids half-flips. We also show that half-flips with [Formula: see text] are 3-avoidable and that half-flips with [Formula: see text] are 2-avoidable.
Authors
- Pascal Ochem (ORCID: https://orcid.org/0000-0001-5504-4586)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Université de Montpellier (FR)
- Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
Publication Details
- Journal
- International Journal of Foundations of Computer Science
- Published
- 2026-10-15
- DOI
- https://doi.org/10.1142/s0129054126500346
- Primary Topic
- semigroups and automata theory
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche