RAIRO - Theoretical Informatics and Applications

A test-set for k-power-free binary morphisms

LaRIA, Université de Picardie Jules Verne, 5 rue du Moulin Neuf, 80000 Amiens, France; wlazinsk@laria.u-picardie.fr.

Abstract

A morphism f is k-power-free if and only if f(w) is k-power-free whenever w is a k-power-free word. A morphism f is k-power-free up to m if and only if f(w) is k-power-free whenever w is a k-power-free word of length at most m. Given an integer k ≥ 2, we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k 2. This bound becomes linear for primitive morphisms: a binary primitive morphism is k-power-free if and only if it is k-power-free up to 2k+1

(Accepted November 2001)

(Online publication August 15 2002)

Key Words:

• Combinatorics on words;
• k-power-free words;
• morphisms;
• test-sets

Mathematics Subject Classification:

• 68R15