More on Square-free Words Obtained from Prefixes by Permutations

Issue title: Russian-Finnish Symposium in Discrete Mathematics

Article type: Research Article

Authors: Ochem, Pascal

Affiliations: LIRMM, CNRS, Univ. Montpellier 2, France. ochem@lirmm.fr

Note: [] Address for correspondence: LIRMM, CNRS, Univ. Montpellier 2, France

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$\dots$ 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.

DOI: 10.3233/FI-2014-1035

Journal: Fundamenta Informaticae, vol. 132, no. 1, pp. 109-112, 2014