Stability of properties of Kolmogorov complexity under relativization
Tóm tắt
Từ khóa
Tài liệu tham khảo
Zvonkin, A.K. and Levin, L.A., Complexity of Finite Objects and the Algorithmic Concepts of Information and Randomness, Uspekhi Mat. Nauk, 1970, vol. 25, no. 6, pp. 85–127 [Russian Math. Surveys (Engl. Transl.), 1970, vol. 25, no. 6, pp. 83–124].
Li, M. and Vitányi, P., An Introduction to Kolmogorov Complexity and Its Applications, New York: Springer, 2008, 3rd ed.
Muchnik, An.A., Conditional Complexity and Codes, Theoret. Comput. Sci., 2002, vol. 271, no. 1–2, pp. 97–109.
Gács, P. and Körner, J., Common Information Is Far Less than Mutual Information, Probl. Control Inform. Theory, 1973, vol. 2, no. 2, pp. 149–162.
Ahlswede, R. and Körner, J., Appendix: On Common Information and Related Characteristics of Correlated Information Sources, General Theory of Information Transfer and Combinatorics, Ahlswede, R., Bäumer, L., Cai, N., Aydinian, H.K., Blinovsky, V., Deppe, C., and Mashurian, H., Eds., Lect. Notes Comp. Sci., vol. 4123, Berlin: Springer, 2006, pp. 664–677.
Chernov, A., Muchnik, An.A., Romashchenko, A., Shen, A., and Vereshchagin, N.K., Upper Semi-lattice of Binary Strings with the Relation “x Is Simple Conditional to y,” Theoret. Comput. Sci., 2002, vol. 271, no. 1–2, pp. 69–95.
Romashchenko, A.E., Pairs of Word with Nonmaterializable Mutual Information, Probl. Peredachi Inf., 2000, vol. 36, no. 1, pp. 3–20 [Probl. Inf. Trans. (Engl. Transl.), 2000, vol. 36, no. 1, pp. 1–18].
Uspensky, V.A. and Shen, A., Relations between Varieties of Kolmogorov Complexities, Math. Syst. Theory, 1996, vol. 29, no. 3, pp. 271–292.
Hammer, D., Romashchenko, A., Shen, A., and Vereshchagin, N., Inequalities for Shannon Entropy and Kolmogorov Complexity, J. Comput. Syst. Sci., 2000, vol. 60, no. 2, pp. 442–464.
Makarychev, K., Makarychev, Yu., Romashchenko, A., and Vereshchagin, N., A New Class of Non-Shannon-type Inequalities for Entropies, Commun. Inf. Syst., 2002, vol. 2, no. 2, pp. 147–162.
Zhang, Z., and Yeung, R.W., On Characterization of Entropy Function via Information Inequalities, IEEE Trans. Inform. Theory, 1998, vol. 44, no. 4, pp. 1440–1452.
Shen’, A.Kh., The Concept of Kolmogorov (α, β)-Stochasticity and Its Properties, Dokl. Akad. Nauk SSSR, 1983, vol. 271, no. 6, pp. 1337–1349 [Soviet Math. Doklady (Engl. Transl.), 1983, vol. 28, pp. 295–299].
Romashchenko, A., Extracting the Mutual Information for a Triple of Binary Strings, in Proc. 18th IEEE Annual Conf. on Computational Complexity (CCC’03), Aarhus, Denmark, 2003, pp. 221–229.
Romashchenko, A.E., A Criterion for Extractability of Mutual Information for a Triple of Strings, Probl. Peredachi Inf., 2003, vol. 39, no. 1, pp. 166–175 [Probl. Inf. Trans. (Engl. Transl.), 2003, vol. 39, no. 1, pp. 148–157].