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

Wlazinski, F.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 437-452

Résumé

A morphism $f$ is $k$-power-free if and only if $f\left(w\right)$ 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\left(w\right)$ is $k$-power-free whenever $w$ is a $k$-power-free word of length at most $m$. Given an integer $k\ge 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$

Détail

Classification : 68R15
Keywords: combinatorics on words, $k$-power-free words, morphisms, test-sets