Skip to Main content Skip to Navigation
Journal articles

Overlap-Freeness in Infinite Partial Words

Vesa Halava 1 Tero Harju 1 Tomi Kärki 1 Patrice Séébold 2, 3
2 ARITH - Arithmétique informatique
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : We prove that there exist infinitely many infinite overlap-free binary partial words containing at least one hole. Moreover, we show that these words cannot contain more than one hole and the only hole must occur either in the first or in the second position.We define that a partial word is k-overlap-free if it does not contain a factor of the form xyxyx where the length of x is at least k. We prove that there exist infinitely many 2-overlap-free binary partial words containing an infinite number of holes.
Document type :
Journal articles
Complete list of metadata

Cited literature [19 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00382675
Contributor : Patrice Séébold <>
Submitted on : Friday, May 22, 2009 - 11:27:56 PM
Last modification on : Thursday, June 10, 2021 - 5:06:46 PM
Long-term archiving on: : Thursday, June 10, 2010 - 10:59:27 PM

File

TCS7276.pdf
Publisher files allowed on an open archive

Identifiers

  • HAL Id : lirmm-00382675, version 1

Citation

Vesa Halava, Tero Harju, Tomi Kärki, Patrice Séébold. Overlap-Freeness in Infinite Partial Words. Theoretical Computer Science, Elsevier, 2009, 410, pp.943-948. ⟨lirmm-00382675⟩

Share

Metrics

Record views

259

Files downloads

281