Reduction in non-(k+1)-power-free morphisms
Wlazinski, Francis1
1 L.A.M.F.A., UMR 7352 du CNRS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80039 Amiens cedex 1, France.
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≥4, a k-power-free uniform morphism is a (k+1)-power-free morphism.

Reçu le :
Accepté le :
DOI : 10.1051/ita/2016006
Classification : 68R15
Mots-clés : Word, morphism, uniform and k-power
Wlazinski, Francis 1

1 L.A.M.F.A., UMR 7352 du CNRS, Université de Picardie Jules Verne, 33 rue Saint-Leu, 80039 Amiens cedex 1, France. 
@article{ITA_2016__50_1_3_0,
     author = {Wlazinski, Francis},
     title = {Reduction in non-($k + 1$)-power-free morphisms},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {3--20},
     publisher = {EDP-Sciences},
     volume = {50},
     number = {1},
     year = {2016},
     doi = {10.1051/ita/2016006},
     mrnumber = {3518156},
     zbl = {1362.68243},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ita/2016006/}
}
TY  - JOUR
AU  - Wlazinski, Francis
TI  - Reduction in non-($k + 1$)-power-free morphisms
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2016
SP  - 3
EP  - 20
VL  - 50
IS  - 1
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ita/2016006/
DO  - 10.1051/ita/2016006
LA  - en
ID  - ITA_2016__50_1_3_0
ER  - 
%0 Journal Article
%A Wlazinski, Francis
%T Reduction in non-($k + 1$)-power-free morphisms
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2016
%P 3-20
%V 50
%N 1
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ita/2016006/
%R 10.1051/ita/2016006
%G en
%F ITA_2016__50_1_3_0
Wlazinski, Francis. Reduction in non-($k + 1$)-power-free morphisms. 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. doi : 10.1051/ita/2016006. https://www.numdam.org/articles/10.1051/ita/2016006/

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. | DOI | MR | Zbl

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

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

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≥0. Discrete Appl. Math. 157 (2009) 2548–2551. | DOI | MR | Zbl

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

J. Karhumäki, On strongly cube-free ω-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 ω-words generated by binary morphisms. Discrete Appl. Math. 5 (1983) 279–297. | DOI | MR | Zbl

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

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. | DOI | MR | Zbl

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. | DOI | MR | Zbl

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

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. | DOI | MR | Zbl

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. | Numdam | Zbl

Cité par Sources :