Length-k-overlap-free Binary Infinite Words - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Article Dans Une Revue Fundamenta Informaticae Année : 2012

Length-k-overlap-free Binary Infinite Words

Résumé

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.
Fichier principal
Vignette du fichier
Seebold_kofiw_revised.pdf (222.34 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

lirmm-00803975 , version 1 (24-03-2013)

Identifiants

Citer

Patrice Séébold. Length-k-overlap-free Binary Infinite Words. Fundamenta Informaticae, 2012, 116, pp.251-263. ⟨10.3233/FI-2012-682⟩. ⟨lirmm-00803975⟩
116 Consultations
319 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More