A test-set for k-power-free binary morphisms
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 35 (2001) no. 5, pp. 437-452.

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 k2, 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
Keywords: combinatorics on words, $k$-power-free words, morphisms, test-sets
@article{ITA_2001__35_5_437_0,
     author = {Wlazinski, F.},
     title = {A test-set for $k$-power-free binary morphisms},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {437--452},
     publisher = {EDP-Sciences},
     volume = {35},
     number = {5},
     year = {2001},
     mrnumber = {1908865},
     zbl = {1010.68102},
     language = {en},
     url = {http://archive.numdam.org/item/ITA_2001__35_5_437_0/}
}
TY  - JOUR
AU  - Wlazinski, F.
TI  - A test-set for $k$-power-free binary morphisms
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2001
SP  - 437
EP  - 452
VL  - 35
IS  - 5
PB  - EDP-Sciences
UR  - http://archive.numdam.org/item/ITA_2001__35_5_437_0/
LA  - en
ID  - ITA_2001__35_5_437_0
ER  - 
%0 Journal Article
%A Wlazinski, F.
%T A test-set for $k$-power-free binary morphisms
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2001
%P 437-452
%V 35
%N 5
%I EDP-Sciences
%U http://archive.numdam.org/item/ITA_2001__35_5_437_0/
%G en
%F ITA_2001__35_5_437_0
Wlazinski, F. A test-set for $k$-power-free binary morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Volume 35 (2001) no. 5, pp. 437-452. http://archive.numdam.org/item/ITA_2001__35_5_437_0/

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