Skip to Main content Skip to Navigation
Journal articles

Length-k-overlap-free Binary Infinite 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 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.
Document type :
Journal articles
Complete list of metadata

Cited literature [11 references]  Display  Hide  Download
Contributor : Patrice Séébold Connect in order to contact the contributor
Submitted on : Sunday, March 24, 2013 - 11:58:11 AM
Last modification on : Friday, August 5, 2022 - 10:45:46 AM
Long-term archiving on: : Sunday, April 2, 2017 - 7:39:10 PM


Publisher files allowed on an open archive



Patrice Séébold. Length-k-overlap-free Binary Infinite Words. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2012, 116, pp.251-263. ⟨10.3233/FI-2012-682⟩. ⟨lirmm-00803975⟩



Record views


Files downloads