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

Institutions

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

Controls
|||
ALL TIME
JAN
FEB
MAR
APR
MAY
JUN
JUL
AUG
SEP
OCT
article

Half-Flips are 5-Avoidable

Pascal Ochem
International Journal of Foundations of Computer Science
semigroups and automata theory
article

Half-Flips are 5-Avoidable

Pascal Ochem
article en

Abstract

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.

International Journal of Foundations of Computer Science
Centre National de la Recherche Scientifique (FR), Université de Montpellier (FR), Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
Agence Nationale de la Recherche
Openalex Percentile: Top 64%
semigroups and automata theory
AI Navigator

Ask Laika to Summarize, Analyze, and Connect papers live on the map.

Summarize Papers & Methodologies

Extract key findings, datasets, and comparative methods across publications.

Benchmark Rankings & Visual Analytics

Rank top research institutions, authors, funders, topics, and journals by Field-Weighted Citation Impact (FWCI) and paper volume with instant charts.

Connect Distant Disciplines

Bridge topological clusters on the map to find hidden collaborative intersections.