Skip to Main content Skip to Navigation
Reports

k-overlap-free binary words

Patrice Séébold 1, 2
1 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Complete list of metadata

Cited literature [9 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512255
Contributor : Patrice Séébold <>
Submitted on : Sunday, August 29, 2010 - 12:29:45 PM
Last modification on : Friday, June 11, 2021 - 3:34:05 AM
Long-term archiving on: : Tuesday, October 23, 2012 - 3:15:50 PM

File

kof_binary_words_V_Hal.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00512255, version 1

Citation

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

Share

Metrics

Record views

204

Files downloads

185