Affiliations: Univ. Montpellier 3 Paul Valéry, Montpellier, F-34199, France | LIRMM, CNRS, F-34392, France, Patrice.Seebold@lirmm.fr
Note: [] Dpt Mathématiques et Informatique Appliquées, Univ. Montpellier 3, Route de Mende, 34199 Montpellier Cedex 5, France; Laboratoire d'Informatique, de Robotique et de Micro-électronique de Montpellier, UMR 5506, CNRS, 161 rue Ada, 34392 Montpellier, France. Address for correspondence: Université Montpellier 3, case H9, Route de Mende, 34199 Montpellier Cedex 5, France
Abstract: We study length-k-overlap-free binary infinite words, i.e., binary infinite words which can contain only overlaps xyxyx with |x| ≤ k − 1. We prove that no such word can be generated by a morphism, except if k = 1. On the other hand, for every k ≥ 2, there exist length-k-overlap-free binary infinite words which are not length-(k − 1)-overlap-free. As an application, we prove that, for every non-negative integer n, there exist infinitely many length-k-overlap-free binary infinite partial words with n holes.
Keywords: Repetition-freeness, length-k-overlaps, partial words, Thue-Morse word, infinite words
