Leroy, J. ; Rigo, M. ; Charlier, E. (éd.)
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.
DOI : 10.1051/ita/2017015
Mots-clés : Morphisms, repetition, cube, k-power
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ita/2017015/
[1] , and , Avoidable patterns in strings of symbols. Pac. J. Math. 85 (1979) 261–294. | DOI | MR | Zbl
[2] , Mots sans carré et morphismes itérés. Discret. Appl. Math. 29 (1980) 235–244. | MR | Zbl
[3] , 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] , Uniformly growing k-th power-free homomorphisms. Theor. Comput. Sci. 23 (1983) 69–82. | DOI | MR | Zbl
[5] , Sharp characterizations of squarefree morphisms. Theor. Comput. Sci. 18 (1982) 221–226. | DOI | MR | Zbl
[6] , Régularités évitables (thèse d’état), Technical Report 83-43. LITP (1983).
[7] and , There are k-uniform cubefree binary morphisms for all k ≥ 0. Discret. Appl. Math. 157 (2009) 2548–2551. | DOI | MR | Zbl
[8] , On cube-free ω-words generated by binary morphisms. Discret. Appl. Math. 5 (1983) 279–297. | DOI | MR | Zbl
[9] , On k-repetition freeness of length uniform morphisms over a binary alphabet. Discret. Appl. Math. 9 (1984) 301–305. | DOI | MR | Zbl
[10] , On the k-freeness of morphisms on free monoids, in Annales Academiae Scientarium Fennicae 61, Series A. (1986). | MR | Zbl
[11] , A characterization of power-free morphisms. Theor. Comput. Sci. 38 (1985) 117–122. | DOI | MR | Zbl
[12] , Codes sans répétition. Ph.D. Thesis, LITP Université Paris 6 (1985).
[13] , 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] , Algebraic Combinatorics on Words. Vol. 90 of Encyclopedia of Mathematics. Cambridge University Press, Cambridge, UK (2002). | Zbl
[15] , Applied Combinatorics on Words. Vol. 105 of Encyclopedia of Mathematics. Cambridge University Press, Cambridge, UK (2005). | MR | Zbl
[16] and , Conjectures and results on morphisms generating k-power-free words. Int. J. Found. Comput. Sci. 15 (2004) 307–316. | DOI | MR | Zbl
[17] and , About cube-free morphisms, in STACS’2000. Vol. 1770 of Lecture Notes in Computer Science, edited by and . Springer-Verlag (2000) 99–109. | DOI | MR | Zbl
[18] and , Some results on k-power-free morphisms. Theor. Comput. Sci. 273 (2002) 119–142. | DOI | MR | Zbl
[19] , Uber unendliche zeichenreihen. Kristiania Videnskapsselskapets Skrifter Klasse I. Mat.-naturv 7 (1906) 1–22. | JFM
[20] , Uber die gegenseitige Lage gleigher Teile gewisser Zeichenreihen. Kristiania Videnskapsselskapets Skrifter Klasse I. Mat.-naturv 1 (1912) 1–67. | JFM
[21] , A test-set for k-power-free binary morphisms. TIA 35 (2001) 437–452. | Numdam | MR | Zbl
[22] , 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 :
