Defect Effect of Bi-infinite Words in the Two-element Case - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Article Dans Une Revue Discrete Mathematics and Theoretical Computer Science Année : 2001

Defect Effect of Bi-infinite Words in the Two-element Case

Résumé

Let X be a two-element set of words over a finite alphabet. If a bi-infinite word possesses two X-factorizations which are not shiftequivalent, then the primitive roots of the words in X are conjugates. Note, that this is a strict sharpening of a defect theorem for bi-infinite words stated in \emphKMP. Moreover, we prove that there is at most one bi-infinite word possessing two different X-factorizations and give a necessary and sufficient conditions on X for the existence of such a word. Finally, we prove that the family of sets X for which such a word exists is parameterizable.
Fichier principal
Vignette du fichier
dm040215.pdf (174.78 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00958962 , version 1 (13-03-2014)

Identifiants

Citer

Ján Maňuch. Defect Effect of Bi-infinite Words in the Two-element Case. Discrete Mathematics and Theoretical Computer Science, 2001, Vol. 4 no. 2 (2), pp.273-290. ⟨10.46298/dmtcs.279⟩. ⟨hal-00958962⟩

Collections

TDS-MACS
37 Consultations
708 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More