CLR cover
Previous problem

Problem 81: Testing Morphism Square-Freeness

Next problem

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.

Show that a morphism $h$ is square free if and only if it is 3-square free and no $h(a)$, $a\in A$, contains a pre-square factor.
Discuss cases using the picture below that displays a square $z^2$ in $h(x)$, where $x=x[0\dd m]$.

Show that for uniform morphisms 3-square-freeness implies square-freeness, and for morphisms from 3-letter alphabets 5-square-freeness implies square-freeness.

References

  • J. Berstel, A. Lauve, C. Reutenauer, and F. Saliola. Combinatorics on Words, volume 27 of CRM Monograph Series. Université de Montréal et American Mathematical Society, Dec. 2008.
  • M. Crochemore. Sharp characterization of square-free morphisms. Theor. Comput. Sci., 18(2):221-226, 1982.
  • M. Lothaire. Combinatorics on Words. Addison-Wesley, 1983. Reprinted in 1997.