$h_1$ is a shortest square-free morphism from $\{\sa{a},\sa{b},\sa{c}\}^*$ to itself, but $h_2$ from $\{\sa{a},\sa{b},\sa{c}\}^*$ to $\{\sa{a},\sa{b},\sa{c},\sa{d},\sa{e}\}^*$ is not square free although it is $4$-square free.
$\cases{ h_1(\sa{a}) = \sa{abcab} &\cr h_1(\sa{b}) = \sa{acabcb} &\cr h_1(\sa{c}) = \sa{acbcacb} }$ | $\cases{ h_2(\sa{a}) = \sa{deabcbda} &\cr h_2(\sa{b}) = \sa{b} &\cr h_2(\sa{c}) = \sa{c} }$ |
Square-free morphisms are word morphisms that preserve word square-freeness. These morphisms provide a useful method to generate by iteration square-free words. The problem aim is to give an effective characterisation of square-free morphisms, which yields a linear-time test according to the morphism length on a fixed-size alphabet.
A square-free morphism $h$ satisfies: $h(x)$ is square free when $x$ is. We also say $h$ is $k$-square free if the condition is satisfied for $|x|\leq k$. In general $k$-square-freeness does not imply square-freeness.
The following characterisation is based on the notion of pre-square. Let $z$ be a factor of $h(a)$, $a\in A$. Its occurrence at position $i$ is called a pre-square if there is a word $y$ for which $ay$ (resp. $ya$) is square free and $z^2$ occurs in $h(ay)$ at position $i$ (resp. in $h(ya)$ with centre $i$). It is clear that if some $h(a)$ has a pre-square $h$ is not a square-free morphism. The converse holds up to an additional condition.