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.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2012, 116, pp.251-263. 〈10.3233/FI-2012-682〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00803975
Contributeur : Patrice Séébold <>
Soumis le : dimanche 24 mars 2013 - 11:58:11
Dernière modification le : jeudi 24 mai 2018 - 15:59:21
Document(s) archivé(s) le : dimanche 2 avril 2017 - 19:39:10

Fichier

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

Identifiants

Collections

Citation

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〉

Partager

Métriques

Consultations de la notice

148

Téléchargements de fichiers

265