Reduction in non-($k+1$)-power-free morphisms

Wlazinski, Francis

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 15th "Journées Montoises d'Informatique Théorique", Tome 50 (2016) no. 1, pp. 3-20

Under some hypotheses, if the image by a morphism of a $(k+1)$-power-free word contains a $(k+1)$-power, we can reduce this word to obtain a new word with the same scheme. These hypotheses are satisfied in the case of uniform morphisms. This allows us to state that, when $k\ge 4$, a $k$-power-free uniform morphism is a $(k+1)$-power-free morphism.

Classification : 68R15
Keywords: Word, morphism, uniform and k-power

J. Berstel, Mots sans carré et morphismes itérés. Discrete Appl. Math. 29 (1980) 235–244. | MR | Zbl

J. Berstel, Axel Thue’s papers on repetition in words: a translation. Technical Report 20, Laboratoire de Combinatoire et d’Informatique Mathématique, Université du Québec, Montréal (1995).

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

F.-J. Brandenburg, Uniformly growing $k$th power-free homomorphisms. Theoret. Comput. Sci. 23(1) (1983) 69–82. | MR | Zbl | DOI

M. Crochemore, Sharp characterizations of squarefree morphisms. Theoret. Comput. Sci. 18 (1982) 221–226. | MR | Zbl | DOI

M. Crochemore, Régularités évitables (thèse d’état). Technical Report 83-43, LITP (1983).

J.D. Currie and N. Rampersad, There are k-uniform cubefree binary morphisms for all $k\ge 0$. Discrete Appl. Math. 157 (2009) 2548–2551. | MR | Zbl | DOI

F. Dejean, Sur un théorème de Thue. J. Comb. Theory 13 (1972) 90–99. series A. | MR | Zbl | DOI

J. Karhumäki, On strongly cube-free $\omega$-words generated by binary morphisms. In Proc. FCT’81. Vol. 117 of Lect. Notes Comput. Sci. Springer, Berlin (1981) 182–189. | MR | Zbl

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

V. Keränen, On $k$-repetition freeness of length uniform morphisms over a binary alphabet. Discrete Appl. Math. 9 (1984) 301–305. | MR | Zbl | DOI

V. Keränen, On the $k$-freeness of morphisms on free monoids. Annales Academiae Scientarium Fennicae. Vol. 61, Series A (1986). | MR | Zbl

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

M. Leconte, Codes sans répétition. Ph.D. thesis, LITP Université Paris 6 (1985).

M. Lothaire, Combinatorics on Words. Vol. 17 of Encyclopedia of Mathematics. Addison-Wesley (1983). Reprinted in 1997 by Cambridge University Press in the Cambridge Mathematical Library, Cambridge, UK (1997). | MR

M. Lothaire, Algebraic Combinatorics on Words. Vol. 90 of Encyclopedia of Mathematics. Cambridge University Press, Cambridge, UK (2002). | Zbl

P.A. Pleasants, Non-repetitive sequences. Mat. Proc. Camb. Phil. Soc. 68 (1970) 267–274. | MR | Zbl | DOI

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

G. Richomme and P. Séébold, Conjectures and results on morphisms generating $k$-power-free words. Int. J. Found. Comput. Sci. 15 (2004) 307–316. | MR | Zbl | DOI

G. Richomme and F. Wlazinski, About cube-free morphisms. In STACS’2000, edited by H. Reichel and S. Tison. Vol. 1770 of Lect. Notes Comput. Sci. Springer-Verlag (2000) 99–109. | MR | Zbl

A. Thue, Uber unendliche zeichenreihen. Kristiania Videnskapsselskapets Skrifter Klasse I. Mat.-naturv 7 (1906) 1–22. | JFM

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

F. Wlazinski, A test-set for $k$-power-free binary morphisms. RAIRO: ITA 35 (2001) 437–452. | Zbl | Numdam