Abstract
Multisource information theory in Shannon setting is well known. In this article we try to develop its algorithmic information theory counterpart and use it as the general framework for many interesting questions about Kolmogorov complexity.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Ahlswede, R., Cai, N., Li, S.-Y.R., Yeung, R.W.: Network information flow. IEEE Trans. Inform. Theory 46, 1004–1016 (2000)
Bennett, C., Gács, P., Li, M., Vitanyi, P., Zurek, W.: Information distance. In: Proc. 25th ACM Symp. Theory of Comput., pp. 21–30 (1993); Final version: IEEE Trans. Inform. Theory IT-44(4), 1407–1423 (1998)
Muchnik, A., Romashchenko, A., Vereshagin, N., Shen, A.: Upper semi-lattice of binary strings with relation x is simple conditional to y. DIMACS Tech. Report, 97-74 (December 1997). Revised version: Proceedings of 1999 Computational Complexity conference, Atlanta. Final version (with A. Chernov): Theoretical Computer Science 271(1–2), 69–95 (2002)
Cziszar, I., Korner, J.: Information theory: Coding Theorems for Discrete Memoryless Systems, 2nd edn. Academic Press, New York (1997)
Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM Journalin Computing 31(3), 887–905 (2002)
Gács, P., Körner, J.: Common information is far less than mutual information. Problems of Control and Information Theory 2(2), 149–162
Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Application, 2nd edn. Springer, Heidelberg (1997)
Li, S.-Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Transactions on Information Theory 49, 371–381 (2003)
Muchnik, A.: Conditional complexity and codes. Theoretical Computer Science 271(1–2), 91–109 (2002)
Muchnik, A., Shen, N., Vereshchagin, M.: Vyugin, Non-reducible descriptions for conditional Kolmogorov complexity. Report TR04-054, Electronic Colloqium on Computational Complexity, ISSN 1433-8092
Hammer, D., Romashenko, A., Shen, A., Vereshchagin, N.: Inequalities for Shannon entropies and Kolmogorov complexities. In: Proceedings of CCC 1997 Conference, Ulm. Final version: Inequalities for Shannon entropy and Kolmogorov Complexity, Journal of Computer and System Sciences, vol. 60, pp. 442–464 (2000)
Romashchenko, A., Shen, A., Vereshchagin, N.: Combinatorial interpretation of Kolmogorov complexity. ECCC Report 7(26) (2000); IEEE conference on Computational Complexity, published in Theoretical Computer Science, vol. 271(1–2), pp. 111–123 (2002)
Shen, A.: Algorithmic Information Theory and Kolmogorov Complexity. Lecture notes of an introductory course. Uppsala University Technical Report (2000-034), Available online at http://www.it.uu.se/research/publications/reports/2000-034
Yeung, R.: A First Course in Information Theory. Springer, Heidelberg (2002)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Shen, A. (2006). Multisource Algorithmic Information Theory. In: Cai, JY., Cooper, S.B., Li, A. (eds) Theory and Applications of Models of Computation. TAMC 2006. Lecture Notes in Computer Science, vol 3959. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11750321_31
Download citation
DOI: https://doi.org/10.1007/11750321_31
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-34021-8
Online ISBN: 978-3-540-34022-5
eBook Packages: Computer ScienceComputer Science (R0)