×

A test-set for \(k\)-power-free binary morphisms. (English) Zbl 1010.68102

Summary: A morphism \(f\) is \(k\)-power-free if and only if \(f(w)\) 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(w)\) is \(k\)-power-free whenever \(w\) is a \(k\)-power-free word of length at most \(m\). Given an integer \(k\geq 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\).

MSC:

68R15 Combinatorics on words

Keywords:

binary morphism
PDFBibTeX XMLCite
Full Text: DOI Numdam EuDML

References:

[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 · Zbl 0824.68093 · doi:10.1016/0166-218X(93)90107-Y
[4] M. Crochemore , Sharp characterizations of squarefree morphisms . Theoret. Comput. Sci. 18 ( 1982 ) 221 - 226 . MR 652471 | Zbl 0482.68085 · Zbl 0482.68085 · doi:10.1016/0304-3975(82)90023-8
[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 · Zbl 0505.03022 · doi:10.1016/0166-218X(83)90002-1
[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 · Zbl 0547.68082 · doi:10.1016/0166-218X(84)90028-3
[7] V. Keränen , On the \(k\)-freeness of morphisms on free monoids . Ann. Acad. Sci. Fenn. 61 ( 1986 ). MR 869270 | Zbl 0604.20056 · Zbl 0604.20056
[8] M. Leconte , A characterization of power-free morphisms . Theoret. Comput. Sci. 38 ( 1985 ) 117 - 122 . MR 805137 | Zbl 0572.68066 · Zbl 0572.68066 · doi:10.1016/0304-3975(85)90213-0
[9] M. Leconte , Codes sans répétition , Ph.D. Thesis. LITP Université P. et M. Curie ( 1985 ). · Zbl 0571.68054
[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 · 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 · Zbl 0514.20045
[12] M. Lothaire , Algebraic combinatorics on words . Cambridge University Press (to appear). MR 1905123 | Zbl 1001.68093 · Zbl 1001.68093
[13] V. Mitrana , Primitive morphisms . Inform. Process. Lett. 64 ( 1997 ) 277 - 281 . MR 1608236 · Zbl 1338.68230
[14] M. Morse , Recurrent geodesics on a surface of negative curvature . Trans. Amer. Math. Soc. 22 ( 1921 ) 84 - 100 . MR 1501161 | JFM 48.0786.06 · JFM 48.0786.06
[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 · Zbl 0946.68114 · doi:10.1016/S0166-218X(99)00118-3
[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 · 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 · Zbl 1014.68127 · doi:10.1016/S0304-3975(00)00437-0
[18] P. Séébold , Sequences generated by infinitely iterated morphisms . Discrete Appl. Math. 11 ( 1985 ) 255 - 264 . MR 792893 | Zbl 0583.20047 · Zbl 0583.20047 · doi:10.1016/0166-218X(85)90077-0
[19] A. Thue , Uber unendliche Zeichenreihen . Videnskapsselskapets Skrifter, I. Mat.-naturv. Klasse, Kristiania ( 1906 ) 1 - 22 . JFM 39.0283.01 · 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 · JFM 44.0462.01
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.