Square-free-preserving and primitive-preserving homomorphisms (Q1878636): Difference between revisions

The authors investigate cube-free- and square-free-preserving homomorphism. A characterization of the latter type of homomorphisms is presented. This characterization provides a method to check whether a non-erasing homomorphism preserves square-free words over an alphabet. It is shown that this method is sometimes more efficient than the classical method implied by an alternative characterization of square-free-preserving homomorphisms due to \textit{M. Crochemore} [Theor. Comput. Sci. 18, 221--226 (1982; Zbl 0482.68085)]. Furthermore, the authors present relationships between square-free-preserving homomorphisms and primitive-preserving homomorphisms. They show that every non-erasing square-free-preserving homomorphism is also primitive-preserving. Properties of the latter type of homomorphisms with an alphabet with two elements are studied, too.