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.
Type de document :
Rapport
[Research Report] RR-10031, Lirmm. 2010
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00512255
Contributeur : Patrice Séébold <>
Soumis le : dimanche 29 août 2010 - 12:29:45
Dernière modification le : jeudi 11 janvier 2018 - 06:26:07
Document(s) archivé(s) le : mardi 23 octobre 2012 - 15:15:50

Fichier

kof_binary_words_V_Hal.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : lirmm-00512255, version 1

Collections

Citation

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

Partager

Métriques

Consultations de la notice

123

Téléchargements de fichiers

76