Square-free words obtained from prefixes by permutations

Abstract

An infinite square-free word w over a three letter alphabet T is said to have a k-stem sigma if w = sigma w(1)w(2) ... where for each i, there exists a permutation pi(i) of T which extended to a morphism gives w(i) = pi(i)(sigma). We show 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. The problem whether k-stem words exist for each k >= 20 remains open. (C) 2011 Elsevier B.V. All rights reserved.