More on square-free words obtained from prefixes by permutations

Pascal Ochem 1
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : 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.
Type de document :
Article dans une revue
Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, Russian-Finnish Symposium in Discrete Mathematics, 132 (1), pp.109-112. 〈10.3233/FI-2014-1035〉
Liste complète des métadonnées

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

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375793
Contributeur : Pascal Ochem <>
Soumis le : lundi 3 octobre 2016 - 15:12:59
Dernière modification le : jeudi 24 mai 2018 - 15:59:22
Document(s) archivé(s) le : vendredi 3 février 2017 - 13:46:11

Fichier

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

Identifiants

Collections

Citation

Pascal Ochem. More on square-free words obtained from prefixes by permutations. Fundamenta Informaticae, Polskie Towarzystwo Matematyczne, 2014, Russian-Finnish Symposium in Discrete Mathematics, 132 (1), pp.109-112. 〈10.3233/FI-2014-1035〉. 〈lirmm-01375793〉

Partager

Métriques

Consultations de la notice

68

Téléchargements de fichiers

101