More on square-free words obtained from prefixes by permutations - 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 : 2014

More on square-free words obtained from prefixes by permutations

Pascal Ochem

Résumé

An infinite square-free word w over the alphabet Σ3 = {0, 1, 2} is said to have a k-stem σ if |σ| = k and w = σw1w2 · · · where for each i, there exists a permutation πi of Σ3 which extended to a morphism gives wi = πi(σ). Harju proved that there exists an infinite k-stem word for k = 1, 2, 3, 9 and 13 ≤ k ≤ 19, but not for 4 ≤ k ≤ 8 and 10 ≤ k ≤ 12. He asked whether k-stem words exist for each k ≥ 20. We give a positive answer to this question. Currie has found another construction that answers Harju's question.
Fichier principal
Vignette du fichier
ochem_stem_FI.pdf (78.03 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

lirmm-01375793 , version 1 (03-10-2016)

Identifiants

Citer

Pascal Ochem. More on square-free words obtained from prefixes by permutations. Fundamenta Informaticae, 2014, Russian-Finnish Symposium in Discrete Mathematics, 132 (1), pp.109-112. ⟨10.3233/FI-2014-1035⟩. ⟨lirmm-01375793⟩
83 Consultations
187 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More