{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T04:41:51Z","timestamp":1760244111678,"version":"build-2065373602"},"reference-count":49,"publisher":"MDPI AG","issue":"4","license":[{"start":{"date-parts":[[2008,11,12]],"date-time":"2008-11-12T00:00:00Z","timestamp":1226448000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/3.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Entropy"],"abstract":"<jats:p>We review the recent progress in the investigation of powerfree words, with particular emphasis on binary cubefree and ternary squarefree words. Besides various bounds on the entropy, we provide bounds on letter frequencies and consider their empirical distribution obtained by an enumeration of binary cubefree words up to length 80.<\/jats:p>","DOI":"10.3390\/e10040590","type":"journal-article","created":{"date-parts":[[2008,11,13]],"date-time":"2008-11-13T10:04:08Z","timestamp":1226570648000},"page":"590-612","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["On the Entropy and Letter Frequencies of Powerfree Words"],"prefix":"10.3390","volume":"10","author":[{"given":"Uwe","family":"Grimm","sequence":"first","affiliation":[{"name":"Department of Mathematics&Statistics, The Open University, Walton Hall, Milton Keynes MK76AA, UK"}]},{"given":"Manuela","family":"Heuer","sequence":"additional","affiliation":[{"name":"Department of Mathematics&Statistics, The Open University, Walton Hall, Milton Keynes MK76AA, UK"}]}],"member":"1968","published-online":{"date-parts":[[2008,11,12]]},"reference":[{"key":"ref_1","unstructured":"Nagell, T., Selberg, A., Selberg, S., and Thalberg, K. (1977). Selected mathematical papers, Universitetsforlaget."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"84","DOI":"10.1090\/S0002-9947-1921-1501161-8","article-title":"Recurrent geodesics on a surface of negative curvature","volume":"22","author":"Morse","year":"1921","journal-title":"Trans. Amer. Math. Soc."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (1997). Combinatorics on words, Cambridge University Press. corrected reprint.","DOI":"10.1017\/CBO9780511566097"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2002). Algebraic combinatorics on words, Cambridge University Press. Encyclopedia of Mathematics and its Applications.","DOI":"10.1017\/CBO9781107326019"},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Lothaire, M. (2005). Applied combinatorics on words, Cambridge University Press. Encyclopedia of Mathematics and its Applications.","DOI":"10.1017\/CBO9781107341005"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"206","DOI":"10.1002\/zamm.19580380510","article-title":"Wiederholungsfreie folgen","volume":"38","author":"Zech","year":"1958","journal-title":"Z. angew. Math. Mech."},{"key":"ref_7","doi-asserted-by":"crossref","first-page":"267","DOI":"10.1017\/S0305004100046077","article-title":"Nonrepetitive sequences","volume":"68","author":"Pleasants","year":"1970","journal-title":"Proc. Cambr. Philos. Soc."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"261","DOI":"10.2140\/pjm.1979.85.261","article-title":"Avoidable patterns in strings of symbols","volume":"95","author":"Bean","year":"1979","journal-title":"Pacific J. Math."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1016\/0304-3975(82)90023-8","article-title":"Sharp characterizations of squarefree morphisms","volume":"18","author":"Crochemore","year":"1982","journal-title":"Theoret. Comput. Sci."},{"key":"ref_10","unstructured":"Cummings, J. L. (1983). Combinatorics on Words, Academic Press."},{"key":"ref_11","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/0304-3975(88)90009-6","article-title":"Uniformly growing k-th power-free homomorphisms","volume":"23","author":"Brandenburg","year":"1983","journal-title":"Theoret. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1093\/qmath\/34.2.145","article-title":"Nonrepetitive sequences on three symbols","volume":"34","author":"Brinkhuis","year":"1983","journal-title":"Quart. J. Math. Oxford Ser. (2)"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1016\/0304-3975(85)90213-0","article-title":"A characterization of power-free morphisms","volume":"38","author":"Leconte","year":"1985","journal-title":"Theoret. Comput. Sci."},{"key":"ref_14","doi-asserted-by":"crossref","first-page":"172","DOI":"10.1007\/3-540-15641-0_33","article-title":"k-th power-free codes","volume":"Vol. 192","author":"Nivat","year":"1985","journal-title":"Automata on Infinite Words"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"207","DOI":"10.1007\/3-540-15641-0_36","article-title":"Overlap-free sequences","volume":"Vol. 192","author":"Nivat","year":"1985","journal-title":"Automata on Infinite Words"},{"key":"ref_16","doi-asserted-by":"crossref","first-page":"175","DOI":"10.1016\/0304-3975(86)90116-7","article-title":"Repetition-free words","volume":"44","author":"Kobayashi","year":"1986","journal-title":"Theoret. Comput. Sci"},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"180","DOI":"10.1007\/BFb0039605","article-title":"On the k-freeness of morphisms on free monoids","volume":"247","year":"1987","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"319","DOI":"10.1016\/0304-3975(89)90071-6","article-title":"Growth problems for avoidable words","volume":"69","author":"Baker","year":"1989","journal-title":"Theoret. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"790","DOI":"10.1080\/00029890.1993.11990489","article-title":"Open problems in pattern avoidance","volume":"100","author":"Currie","year":"1993","journal-title":"Amer. Math. Monthly"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"161","DOI":"10.1016\/S0304-3975(98)00257-6","article-title":"On repetition-free binary words of minimal density","volume":"218","author":"Kolpakov","year":"1999","journal-title":"Theoret. Comput. Sci."},{"key":"ref_21","unstructured":"Grimm, U. (2001). Improved bounds on the number of ternary square-free words. J. Integer Seq., 4, (2), Article 01.2.7."},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"#N10","DOI":"10.37236\/1671","article-title":"There are circular square-free words of length n for n\u226518","volume":"9","author":"Currie","year":"2002","journal-title":"Electron. J. Combin."},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"119","DOI":"10.1016\/S0304-3975(00)00437-0","article-title":"Some results on k-power-free morphisms","volume":"273","author":"Richomme","year":"2002","journal-title":"Theoret. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"#R12","DOI":"10.37236\/1705","article-title":"How many square occurrences must a binary sequence contain?","volume":"10","author":"Kucherov","year":"2003","journal-title":"Electron. J. Combin."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"335","DOI":"10.1016\/j.jcta.2003.12.004","article-title":"Polynomial versus exponential growth in repetition-free binary words","volume":"105","author":"Shallit","year":"2004","journal-title":"J. Combin. Theory Ser. A"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"#R14","DOI":"10.37236\/1767","article-title":"On the entropy and letter frequencies of ternary square-free words","volume":"11","author":"Richard","year":"2004","journal-title":"Electron. J. Combin."},{"key":"ref_27","unstructured":"Ochem, P., and Reix, T. (2006). Presented at the Workshop on Words and Automata (WOWA\u201906)."},{"key":"ref_28","doi-asserted-by":"crossref","first-page":"2001","DOI":"10.1016\/j.dam.2007.04.024","article-title":"Existence of finite test-sets for k-powerfreeness of uniform morphims","volume":"155","author":"Richomme","year":"2007","journal-title":"Discrete Applied Math."},{"key":"ref_29","unstructured":"Kolpakov, R. (2007). Efficient lower bounds on the number of repetition-free words. J. Integer Seq., 10, (3), Article 07.3.2."},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.tcs.2007.03.027","article-title":"Letter frequency in infinite repetition-free words","volume":"380","author":"Ochem","year":"2007","journal-title":"Theoret. Comput. Sci."},{"key":"ref_31","doi-asserted-by":"crossref","unstructured":"Chalopin, J., and Ochem, P. (2007). Dejean\u2019s conjecture and letter frequency. Electronic Notes in Discrete Mathematics, 501\u2013505.","DOI":"10.1016\/j.endm.2007.01.068"},{"key":"ref_32","unstructured":"Ochem, P. (,  2007). Unequal letter frequencies in ternary square-free words. Proceedings of 6th International Conference on Words (WORDS 2007), Marseille."},{"key":"ref_33","unstructured":"Khalyavin, A. (2007). The minimal density of a letter in an infinite ternary square-free word is \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t              883\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t              3215\n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t            \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t          \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t        \n\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t\t      . J. Integer Seq., 10, Article 07.6.5."},{"key":"ref_34","doi-asserted-by":"crossref","unstructured":"Queff\u00e9lec, M. (1987). Substitution dynamical systems\u2014spectral analysis, Springer-Verlag. Lecture Notes in Mathematics.","DOI":"10.1007\/BFb0081890"},{"key":"ref_35","unstructured":"Berth\u00e9, V., Ferenczi, S., Mauduit, C., and Siegel, A. (2002). Substitutions in dynamics, arithmetics and combinatorics, Springer-Verlag. Lecture Notes in Mathematics."},{"key":"ref_36","doi-asserted-by":"crossref","unstructured":"Allouche, J.-P., and Shallit, J. (2003). Automatic sequences, Cambridge University Press.","DOI":"10.1017\/CBO9780511546563"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Moody, R. V. (1997). The mathematics of long-range aperiodic order, Kluwer Academic Publishers Group. NATO Advanced Science Institutes Series C: Mathematical and Physical Sciences.","DOI":"10.1007\/978-94-015-8784-6"},{"key":"ref_38","doi-asserted-by":"crossref","first-page":"338","DOI":"10.1007\/BFb0015759","article-title":"On k-repetition free words generated by length uniform morphisms over a binary alphabet","volume":"194","year":"1985","journal-title":"Lecture Notes in Computer Science"},{"key":"ref_39","doi-asserted-by":"crossref","first-page":"13","DOI":"10.1016\/S0895-7177(97)00196-9","article-title":"The entropy of square-free words","volume":"26","author":"Baake","year":"1997","journal-title":"Math. Comput. Modelling"},{"key":"ref_40","doi-asserted-by":"crossref","unstructured":"Walters, P. (1982). An introduction to ergodic theory, Springer-Verlag.","DOI":"10.1007\/978-1-4612-5775-2"},{"key":"ref_41","doi-asserted-by":"crossref","first-page":"355","DOI":"10.1080\/10236199908808197","article-title":"The goulden-jackson cluster method: Extensions, applications, and implementations","volume":"5","author":"Noonan","year":"1999","journal-title":"J. Difference Eq. Appl."},{"key":"ref_42","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1016\/j.tcs.2005.03.039","article-title":"Growth of repetition-free words \u2013 a review","volume":"340","author":"Berstel","year":"2005","journal-title":"Theoret. Comput. Sci."},{"key":"ref_43","unstructured":"Elser, V. (1983). Repeat-free sequences. Lawrence Berkeley Laboratory report, LBL-16632."},{"key":"ref_44","unstructured":"Sun, X. (2003). New lower-bound on the number of ternary square-free words. J Integer Seq., 6, Article 03.3.2."},{"key":"ref_45","doi-asserted-by":"crossref","first-page":"353","DOI":"10.1080\/10236199908808196","article-title":"The number of binary cube-free words of length up to 47 and their numerical analysis","volume":"5","author":"Edlin","year":"1999","journal-title":"J. Differ. Equations Appl."},{"key":"ref_46","unstructured":"Titchmarsh, E. C. (1976). The theory of functions, Oxford University Press."},{"key":"ref_47","unstructured":"Ekhad, S., and Zeilberger, D. (1998). There are more than 2n\/17 n-letter ternary square-free words. J. Integer Seq., 1, Article 98.1.9."},{"key":"ref_48","doi-asserted-by":"crossref","first-page":"1527","DOI":"10.1142\/S021797929300247X","article-title":"Trace maps, invariants, and some of their applications","volume":"7","author":"Baake","year":"1993","journal-title":"Int. J. Mod. Phys. B"},{"key":"ref_49","unstructured":"Tarannikov, Y. (2002). The minimal density of a letter in an infinite ternary square-free words is 0.2746\u2026. J. Integer Seq., 5, Article 02.2.2."}],"container-title":["Entropy"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1099-4300\/10\/4\/590\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T22:21:08Z","timestamp":1760221268000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1099-4300\/10\/4\/590"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11,12]]},"references-count":49,"journal-issue":{"issue":"4","published-online":{"date-parts":[[2008,12]]}},"alternative-id":["e10040590"],"URL":"https:\/\/doi.org\/10.3390\/e10040590","relation":{},"ISSN":["1099-4300"],"issn-type":[{"type":"electronic","value":"1099-4300"}],"subject":[],"published":{"date-parts":[[2008,11,12]]}}}