A test-set for $k$-power-free binary morphisms
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
@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},
zbl = {1010.68102},
mrnumber = {1908865},
language = {en},
url = {http://www.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
DA  - 2001///
SP  - 437
EP  - 452
VL  - 35
IS  - 5
PB  - EDP-Sciences
UR  - http://www.numdam.org/item/ITA_2001__35_5_437_0/
UR  - https://zbmath.org/?q=an%3A1010.68102
UR  - https://www.ams.org/mathscinet-getitem?mr=1908865
LA  - en
ID  - ITA_2001__35_5_437_0
ER  - 
Wlazinski, F. A test-set for $k$-power-free binary morphisms. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 35 (2001) no. 5, pp. 437-452. http://www.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 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