RAIRO - Theoretical Informatics and Applications

Table of Contents - September 2001 - Volume 35, Issue 05  

Research Article

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

Wlazinski, F.

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

(Received May 2001)

(Accepted November 2001)

(Online publication August 15 2002)

Key Words:

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

Mathematics Subject Classification:

  • 68R15