Words avoiding the morphic images of most of their factors
We say that a finite factor $f$ of a word $w$ is \emph{imaged} if there exists a non-erasing morphism $m$, distinct from the identity, such that $w$ contains $m(f)$. We show that every infinite word contains an imaged factor of length at least 6 and that 6 is best possible. We show that every infinite binary word contains at least 36 distinct imaged factors and that 36 is best possible.
Authors
- Pascal Ochem (ORCID: https://orcid.org/0000-0001-5504-4586)
- Matthieu Rosenfeld (ORCID: https://orcid.org/0000-0001-5467-5407)
Institutions
- Centre National de la Recherche Scientifique (FR)
- Laboratoire d'Informatique, de Robotique et de Microélectronique de Montpellier (FR)
Publication Details
- Journal
- Discrete Mathematics & Theoretical Computer Science
- Published
- 2025-09-23
- DOI
- https://doi.org/10.46298/dmtcs.15919
- Primary Topic
- Natural Language Processing Techniques
- Type
- article
- Field-Weighted Citation Impact
- 0.00
Funders
- Agence Nationale de la Recherche