Issue Theoret. Informatics Appl. Volume 35, Number 5, September-October 2001 Page(s) 437 - 452 DOI 10.1051/ita:2001104

DOI: 10.1051/ita:2001104


Theoret. Informatics Appl. 35, 437-452 (2001)

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

F. Wlazinski

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

(Received May, 2001. Accepted November, 2001.)

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 , we prove that a binary morphism is k-power-free if and only if it is k-power-free up to k². 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

Mathematics Subject Classification. 68R15.

Key words: Combinatorics on words -- k-power-free words -- morphisms -- test-sets


© EDP Sciences 2001

What is OpenURL?