Rivals, E.; Delahaye, J.-P. Optimal representation in average using Kolmogorov complexity. (English) Zbl 0915.68093 Theor. Comput. Sci. 200, No. 1-2, 261-287 (1998). Summary: One knows from the algorithmic complexity nLab Wikipedia theory that a word is incompressible on average. For words of pattern \(x^m\), it is natural to believe that providing \(x\) and \(m\) is an optimal average representation. On the contrary, for words like \(x\oplus y\) (i.e., the bit to bit \(x\) or between \(x\) and \(y\)), providing \(x\) and \(y\) is not an optimal description on average. In this work, we sketch a theory of average optimal representation that formalizes natural ideas and operates where intuition does not suffice. First, we formulate a definition of \(K\)-optimality on average for a pattern, then demonstrate results that corroborate intuitive ideas, and give worthy insights into the best compression in more complex cases. MSC: 68Q30 Algorithmic information theory (Kolmogorov complexity, etc.) Keywords:algorithmic complexity theory; \(K\)-optimality on average × Cite Format Result Cite Review PDF Full Text: DOI References: [1] Bell, T. C.; Cleary, J. G.; Witten, I. H., Text Compression, 1990, Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ [2] Calude, C., Information and Randomness: an Algorithmic Perspective, 1994, Springer: Springer Berlin · Zbl 0922.68073 [3] Cover, T. M.; Thomas, J. A., Information Theory [4] Crochemore, M.; Rytter, W., Text Algorithms, 1994, Oxford University Press: Oxford University Press Oxford · Zbl 0844.68101 [5] Delahaye, J.-P., Information, complexité et hasard, 1994, Hermès: Hermès Paris [6] Goldberg, A. V.; Sipser, M., Compression and Ranking, SIAM J. Comput., 20, 524-536, 1991 · Zbl 0738.68048 [7] Huffman, D. A., A method for the construction of minimum redundancy codes, 1098-1101 · Zbl 0137.13605 [8] Li, M.; Vitanyi, P. M.B., Introduction to Kolmogorov Complexity and Its Applications, 1997, Springer: Springer Berlin · Zbl 0866.68051 [9] Milosavljevic̀, A., Discovering sequence similarity by the algorithmic significance, 284-291 [10] Rivals, É.; Dauchet, M.; Delahaye, J.-P.; Delgrange, O., Compression and genetic sequences analysis, Biochimie, 78, 4, 315-322, 1996 [11] Rivals, É.; Delgrange, O.; Delahaye, J-P.; Dauchet, M.; Delorme, M. O.; Hénaut, A.; Ollivier, E., Detection of significant patterns by compression algorithms: the case of Approximate Tandem Repeats in DNA sequences, CABIOS, 13, 2, 131-136, 1997 [12] Shannon, C. E., A mathematical theory of communications, Bell System Tech. J., 27, 379-423, 1948; Shannon, C. E., A mathematical theory of communications, Bell System Tech. J., 27, 623-656, 1948 · Zbl 1154.94303 [13] Storer, J. A., Data Compression: Methods and Theory, 1988, Computer Sciences Press: Computer Sciences Press Rockville, MD [14] Watanabe, O., Kolmogorov Complexity and Computational Complexity, 1992, Springer: Springer Berlin · Zbl 0755.68017 [15] Yockey, P. H., Information Theory and Molecular Biology, 1992, Cambridge Univ. Press: Cambridge Univ. Press Cambridge · Zbl 0759.92004 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.