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

Wlazinski, F.

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001), p. 437-452 / Harvested from Numdam

Résumé

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 \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

Publié le : 2001-01-01

MR 1908865 | Zbl 1010.68102

Classification:  68R15

Bibliographie

[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 1243728 | Zbl 0824.68093

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

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

[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 763566 | Zbl 0547.68082

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

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

[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 0221.20076

[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 0514.20045

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

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

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

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

[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 1781724 | Zbl 0959.68532

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

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

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

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