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.
Document type :
Journal articles
Complete list of metadatas

Cited literature [5 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-01375793
Contributor : Pascal Ochem <>
Submitted on : Monday, October 3, 2016 - 3:12:59 PM
Last modification on : Thursday, May 24, 2018 - 3:59:22 PM
Long-term archiving on : Friday, February 3, 2017 - 1:46:11 PM

File

ochem_stem_FI.pdf
Files produced by the author(s)

Identifiers

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⟩

Share

Metrics

Record views

116

Files downloads

197