On the entropy and letter frequencies of powerfree words. (English) Zbl 1179.68112
Summary: 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.
MSC:
| 68R15 | Combinatorics on words |
| 11B85 | Automata sequences |
| 37B10 | Symbolic dynamics |
| 94A17 | Measures of information, entropy |
Keywords:
entropy and information theory; symbolic sequences; combinatorics on words; integer sequencesReferences:
| [1] | Thue, Selected mathematical papers (1977) |
| [2] | DOI: 10.1090/S0002-9947-1921-1501161-8 · doi:10.1090/S0002-9947-1921-1501161-8 |
| [3] | Lothaire, Combinatorics on words (1997) |
| [4] | Lothaire, Algebraic combinatorics on words (2002) |
| [5] | Lothaire, Applied combinatorics on words (2005) |
| [6] | DOI: 10.1002/zamm.19580380510 · doi:10.1002/zamm.19580380510 |
| [7] | DOI: 10.1017/S0305004100046077 · doi:10.1017/S0305004100046077 |
| [8] | DOI: 10.2140/pjm.1979.85.261 · Zbl 0428.05001 · doi:10.2140/pjm.1979.85.261 |
| [9] | DOI: 10.1016/0304-3975(82)90023-8 · Zbl 0482.68085 · doi:10.1016/0304-3975(82)90023-8 |
| [10] | Shelton, On the structure and extendibility of squarefree words, Combinatorics on Words pp 101– (1983) · Zbl 0561.68054 |
| [11] | DOI: 10.1016/0304-3975(88)90009-6 · Zbl 0508.68051 · doi:10.1016/0304-3975(88)90009-6 |
| [12] | DOI: 10.1093/qmath/34.2.145 · Zbl 0528.05004 · doi:10.1093/qmath/34.2.145 |
| [13] | DOI: 10.1016/0304-3975(85)90213-0 · Zbl 0572.68066 · doi:10.1016/0304-3975(85)90213-0 |
| [14] | Leconte, k-th power-free codes, Automata on Infinite Words Vol. 192 pp 172– (1985) |
| [15] | Séébold, Overlap-free sequences, Automata on Infinite Words Vol. 192 pp 207– (1985) |
| [16] | DOI: 10.1016/0304-3975(86)90116-7 · Zbl 0596.20058 · doi:10.1016/0304-3975(86)90116-7 |
| [17] | Keräenen, On the k-freeness of morphisms on free monoids, Lecture Notes in Computer Science 247 pp 180– (1987) · Zbl 0615.20051 · doi:10.1007/BFb0039605 |
| [18] | DOI: 10.1016/0304-3975(89)90071-6 · Zbl 0693.68039 · doi:10.1016/0304-3975(89)90071-6 |
| [19] | DOI: 10.2307/2324790 · Zbl 0798.68139 · doi:10.2307/2324790 |
| [20] | DOI: 10.1016/S0304-3975(98)00257-6 · Zbl 0916.68118 · doi:10.1016/S0304-3975(98)00257-6 |
| [21] | Grimm, Improved bounds on the number of ternary square-free words, J. Integer Seq. 4 (2) (2001) · Zbl 1004.05003 |
| [22] | Currie, There are circular square-free words of length n for n8, Electron. J. Combin. 9 pp #N10– (2002) · Zbl 1057.68081 |
| [23] | DOI: 10.1016/S0304-3975(00)00437-0 · Zbl 1014.68127 · doi:10.1016/S0304-3975(00)00437-0 |
| [24] | Kucherov, How many square occurrences must a binary sequence contain?, Electron. J. Combin. 10 pp #R12– (2003) · Zbl 1011.05007 |
| [25] | DOI: 10.1016/j.jcta.2003.12.004 · Zbl 1065.68080 · doi:10.1016/j.jcta.2003.12.004 |
| [26] | Richard, On the entropy and letter frequencies of ternary square-free words, Electron. J. Combin. 11 (1) pp #R14– (2004) · Zbl 1104.68090 |
| [27] | Ochem, Upper bound on the number of ternary square-free words (2006) |
| [28] | DOI: 10.1016/j.dam.2007.04.024 · Zbl 1129.68053 · doi:10.1016/j.dam.2007.04.024 |
| [29] | Kolpakov, Efficient lower bounds on the number of repetition-free words, J. Integer Seq. 10 (3) (2007) · Zbl 1118.05003 |
| [30] | DOI: 10.1016/j.tcs.2007.03.027 · Zbl 1115.68124 · doi:10.1016/j.tcs.2007.03.027 |
| [31] | DOI: 10.1016/j.endm.2007.01.068 · Zbl 1291.68300 · doi:10.1016/j.endm.2007.01.068 |
| [33] | Khalyavin, The minimal density of a letter in an infinite ternary square-free word is 8833215, J. Integer Seq. 10 (2007) · Zbl 1140.11304 |
| [34] | Queffélec, Substitution dynamical systems–spectral analysis (1987) · Zbl 0642.28013 |
| [35] | Fogg, Substitutions in dynamics, arithmetics and combinatorics (2002) · Zbl 1014.11015 |
| [36] | Allouche, Automatic sequences (2003) · Zbl 1086.11015 |
| [37] | Moody, The mathematics of long-range aperiodic order Vol. 489 (1997) · Zbl 0861.00015 |
| [38] | Keränen, On k-repetition free words generated by length uniform morphisms over a binary alphabet, Lecture Notes in Computer Science 194 pp 338– (1985) · Zbl 0571.68055 · doi:10.1007/BFb0015759 |
| [39] | DOI: 10.1016/S0895-7177(97)00196-9 · Zbl 1185.68502 · doi:10.1016/S0895-7177(97)00196-9 |
| [40] | Walters, An introduction to ergodic theory (1982) · Zbl 0475.28009 |
| [41] | DOI: 10.1080/10236199908808197 · Zbl 0935.05003 · doi:10.1080/10236199908808197 |
| [42] | DOI: 10.1016/j.tcs.2005.03.039 · Zbl 1078.68112 · doi:10.1016/j.tcs.2005.03.039 |
| [43] | Elser, Repeat-free sequences, Lawrence Berkeley Laboratory report LBL-16632 (1983) |
| [44] | Sun, New lower-bound on the number of ternary square-free words, J Integer Seq. 6 (2003) · Zbl 1024.05004 |
| [45] | DOI: 10.1080/10236199908808196 · Zbl 0939.05007 · doi:10.1080/10236199908808196 |
| [46] | Titchmarsh, The theory of functions (1976) · Zbl 0005.21004 |
| [47] | Ekhad, There are more than 2n/17n-letter ternary square-free words, J. Integer Seq. 1 (1998) · Zbl 1018.68060 |
| [48] | DOI: 10.1142/S021797929300247X · Zbl 0799.22011 · doi:10.1142/S021797929300247X |
| [49] | Tarannikov, The minimal density of a letter in an infinite ternary square-free words is 0.2746..., J. Integer Seq. 5 (2002) · Zbl 1121.11303 |
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.
