k-overlap-free binary words - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Reports (Research Report) Year : 2010

k-overlap-free binary words


We study k-overlap-free binary infinite words that are binary infinite words which can contain only overlaps xyxyx with |x| ≤ k-1. We prove that no such word can be generated by morphism, except if k = 1. On the other hand, for every k ≥ 2, there exist k-overlap-free binary infinite words which are not (k-1)-overlap-free. As an application, we prove that, for every integer n, there exists infinitely many k-overlap-free binary infinite partial words with n holes.
Fichier principal
Vignette du fichier
kof_binary_words_V_Hal.pdf (149.03 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-00512255 , version 1 (29-08-2010)


  • HAL Id : lirmm-00512255 , version 1


Patrice Séébold. k-overlap-free binary words. [Research Report] RR-10031, Lirmm. 2010. ⟨lirmm-00512255⟩
87 View
105 Download


Gmail Facebook X LinkedIn More