Restricted Square Property and Infinite Partial Words

Patrice Séébold 1, 2 Vesa Halava 3 Tero Harju 3 Tomi Kärki 3
1 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 :
Rapport
[Research Report] RR-09025/930, Lirmm; Turku Centre for Computer Science. 2009, pp.16
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00408116
Contributeur : Patrice Séébold <>
Soumis le : mardi 25 août 2009 - 12:20:45
Dernière modification le : jeudi 24 mai 2018 - 15:59:21

Identifiants

  • HAL Id : lirmm-00408116, version 1

Collections

Citation

Patrice Séébold, Vesa Halava, Tero Harju, Tomi Kärki. Restricted Square Property and Infinite Partial Words. [Research Report] RR-09025/930, Lirmm; Turku Centre for Computer Science. 2009, pp.16. 〈lirmm-00408116〉

Partager

Métriques

Consultations de la notice

97