A uniform cube-free morphism is k-power-free for all integers k ≥ 4

Leroy, J. ;  Rigo, M. ;  Charlier, E. (éd.)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 205-216.

In the study of k-power-free morphisms, the case of 3-free-morphisms, i.e., cube-free morphisms, often differs from other k-power-free morphisms. Indeed, cube-freeness is less restrictive than square-freeness. And a cube provides less equations to solve than any integer k ≥ 4. Anyway, the fact that the image of a word by a morphism contains a cube implies relations that, under some assumptions, allow us to establish our main result: a cube-free uniform morphism is a k-power-free morphism for all integers k ≥ 4.

Accepté le :
DOI : 10.1051/ita/2017015
Classification : 68R15
Mots-clés : Morphisms, repetition, cube, k-power
Wlazinski, Francis 1

1 
@article{ITA_2017__51_4_205_0,
     author = {Wlazinski, Francis},
     editor = {Leroy, J. and Rigo, M. and Charlier, E.},
     title = {A uniform cube-free morphism is k-power-free for all integers k \ensuremath{\geq} 4},
     journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
     pages = {205--216},
     publisher = {EDP-Sciences},
     volume = {51},
     number = {4},
     year = {2017},
     doi = {10.1051/ita/2017015},
     mrnumber = {3782821},
     zbl = {1453.68147},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ita/2017015/}
}
TY  - JOUR
AU  - Wlazinski, Francis
ED  - Leroy, J.
ED  - Rigo, M.
ED  - Charlier, E.
TI  - A uniform cube-free morphism is k-power-free for all integers k ≥ 4
JO  - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY  - 2017
SP  - 205
EP  - 216
VL  - 51
IS  - 4
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ita/2017015/
DO  - 10.1051/ita/2017015
LA  - en
ID  - ITA_2017__51_4_205_0
ER  - 
%0 Journal Article
%A Wlazinski, Francis
%E Leroy, J.
%E Rigo, M.
%E Charlier, E.
%T A uniform cube-free morphism is k-power-free for all integers k ≥ 4
%J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
%D 2017
%P 205-216
%V 51
%N 4
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ita/2017015/
%R 10.1051/ita/2017015
%G en
%F ITA_2017__51_4_205_0
Wlazinski, Francis. A uniform cube-free morphism is k-power-free for all integers k ≥ 4. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Special issue dedicated to the 16th "Journées Montoises d’Informatique Théorique", Tome 51 (2017) no. 4, pp. 205-216. doi : 10.1051/ita/2017015. http://archive.numdam.org/articles/10.1051/ita/2017015/

[1] D.R. Bean, A. Ehrenfeucht and G.F. Mcnulty, Avoidable patterns in strings of symbols. Pac. J. Math. 85 (1979) 261–294. | DOI | MR | Zbl

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

[3] 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).

[4] F.-J. Brandenburg, Uniformly growing k-th power-free homomorphisms. Theor. Comput. Sci. 23 (1983) 69–82. | DOI | MR | Zbl

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

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

[7] J.D. Currie and N. Rampersad, There are k-uniform cubefree binary morphisms for all k ≥ 0. Discret. Appl. Math. 157 (2009) 2548–2551. | DOI | MR | Zbl

[8] J. Karhumäki, On cube-free ω-words generated by binary morphisms. Discret. Appl. Math. 5 (1983) 279–297. | DOI | MR | Zbl

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

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

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

[12] M. Leconte, Codes sans répétition. Ph.D. Thesis, LITP Université Paris 6 (1985).

[13] 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

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

[15] M. Lothaire, Applied Combinatorics on Words. Vol. 105 of Encyclopedia of Mathematics. Cambridge University Press, Cambridge, UK (2005). | MR | Zbl

[16] 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

[17] G. Richomme and F. Wlazinski, About cube-free morphisms, in STACS’2000. Vol. 1770 of Lecture Notes in Computer Science, edited byH. Reichel and S. Tison. Springer-Verlag (2000) 99–109. | DOI | MR | Zbl

[18] G. Richomme and F. Wlazinski, Some results on k-power-free morphisms. Theor. Comput. Sci. 273 (2002) 119–142. | DOI | MR | Zbl

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

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

[21] F. Wlazinski, A test-set for k-power-free binary morphisms. TIA 35 (2001) 437–452. | Numdam | MR | Zbl

[22] F. Wlazinski, Reduction in non-(k + 1)-power-free morphisms. Special issue dedicated to the 15th “Journées montoises d’informatique théorique”. RAIRO: ITA 50 (2016) 3–20. | Numdam | MR

Cité par Sources :