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.

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$

Classification : 68R15
Mots clés : combinatorics on words, $k$-power-free words, morphisms, test-sets

[1] J. Berstel, Axel thue's work on repetitions in words, edited by P. Leroux and C. Reutenauer, Séries formelles et combinatoire algébrique. LaCIM, University of Québec at Montréal (1992) 65-80.

[2] J. Berstel, Axel thue's papers on repetitions in words: A translation, Technical Report 20. LaCIM, University of Québec at Montréal (1995).

[3] J. Berstel and P. Séébold, A characterization of overlap-free morphisms. Discrete Appl. Math. 46 (1993) 275-281. | MR | Zbl

[4] M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci. 18 (1982) 221-226. | MR | Zbl

[5] J. Karhumäki, On cube free $\omega$-words generated by binary morphisms. Discrete Appl. Math. 5 (1983) 279-297. | MR | Zbl

[6] V. Keränen, On the $k$-repetition freeness of length uniform morphisms over a binary alphabet. Discrete Appl. Math. 9 (1984) 297-300. | MR | Zbl

[7] V. Keränen, On the $k$-freeness of morphisms on free monoids. Ann. Acad. Sci. Fenn. 61 (1986). | MR | Zbl

[8] M. Leconte, A characterization of power-free morphisms. Theoret. Comput. Sci. 38 (1985) 117-122. | MR | Zbl

[9] M. Leconte, Codes sans répétition, Ph.D. Thesis. LITP Université P. et M. Curie (1985).

[10] A. Lentin and M.P. Schützenberger, A combinatorial problem in the theory of free monoids, edited by R.C. Bose and T.E. Dowling. Chapell Hill, North Carolina Press edition, Comb. Math. (1945) 112-144. | Zbl

[11] M. Lothaire, Combinatorics on words, Vol. 17 of Encyclopedia of Mathematics, Chap. 9, Equations on words. Addison-Wesley (1983). Reprinted in 1997 by Cambridge University Press in the Cambridge Mathematical Library. | Zbl

[12] M. Lothaire, Algebraic combinatorics on words. Cambridge University Press (to appear). | MR | Zbl

[13] V. Mitrana, Primitive morphisms. Inform. Process. Lett. 64 (1997) 277-281. | MR

[14] M. Morse, Recurrent geodesics on a surface of negative curvature. Trans. Amer. Math. Soc. 22 (1921) 84-100. | JFM | MR

[15] G. Richomme and P. Séébold, Characterization of test-sets for overlap-free morphisms. Discrete Appl. Math. 98 (1999) 151-157. | MR | Zbl

[16] G. Richomme and F. Wlazinski, About cube-free morphisms, edited by H. Reichel and S. Tison, STACS 2000. Springer-Verlag, Lecture Notes in Comput. Sci. 1770 (2000) 99-109. | MR | Zbl

[17] G. Richomme and F. Wlazinski, Some results on $k$-power-free morphisms. Theoret. Comput. Sci. 273 (2002) 119-142. | MR | Zbl

[18] P. Séébold, Sequences generated by infinitely iterated morphisms. Discrete Appl. Math. 11 (1985) 255-264. | MR | Zbl

[19] A. Thue, Uber unendliche Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1906) 1-22. | JFM

[20] A. Thue, Uber die gegenseitige Lage gleigher Teile gewisser Zeichenreihen. Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania (1912) 1-67. | JFM