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.
Type de document :
Article dans une revue
Theoretical Computer Science, Elsevier, 2009, 410, pp.943-948
Liste complète des métadonnées

Littérature citée [19 références]  Voir  Masquer  Télécharger

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00382675
Contributeur : Patrice Séébold <>
Soumis le : vendredi 22 mai 2009 - 23:27:56
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : jeudi 10 juin 2010 - 22:59:27

Fichier

TCS7276.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : lirmm-00382675, version 1

Collections

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〉

Partager

Métriques

Consultations de la notice

173

Téléchargements de fichiers

94