Problem 81: Testing Morphism Square-Freeness

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 satisfies: is square free when is. We also say is -square free if the condition is satisfied for . In general -square-freeness does not imply square-freeness.

The following characterisation is based on the notion of pre-square. Let be a factor of , . Its occurrence at position is called a pre-square if there is a word for which (resp. ) is square free and occurs in at position (resp. in with centre ). It is clear that if some has a pre-square is not a square-free morphism. The converse holds up to an additional condition.

Show that a morphism

is square free if and only if it is 3-square free and no

, contains a pre-square factor.

Discuss cases using the picture below that displays a square

, where

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.

125 Problems in Text Algorithms

Example

Problem 81: Testing Morphism Square-Freeness

References