Multisource Algorithmic Information Theory | SpringerLink
Skip to main content

Multisource Algorithmic Information Theory

  • Conference paper
Theory and Applications of Models of Computation (TAMC 2006)

Part of the book series: Lecture Notes in Computer Science ((LNTCS,volume 3959))

  • 1085 Accesses

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

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 11439
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 14299
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Ahlswede, R., Cai, N., Li, S.-Y.R., Yeung, R.W.: Network information flow. IEEE Trans. Inform. Theory 46, 1004–1016 (2000)

    Article  MathSciNet  Google Scholar 

  2. 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)

    Google Scholar 

  3. 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)

    Google Scholar 

  4. Cziszar, I., Korner, J.: Information theory: Coding Theorems for Discrete Memoryless Systems, 2nd edn. Academic Press, New York (1997)

    Google Scholar 

  5. Buhrman, H., Fortnow, L., Laplante, S.: Resource-bounded Kolmogorov complexity revisited. SIAM Journalin Computing 31(3), 887–905 (2002)

    Article  MATH  MathSciNet  Google Scholar 

  6. Gács, P., Körner, J.: Common information is far less than mutual information. Problems of Control and Information Theory 2(2), 149–162

    Google Scholar 

  7. Li, M., Vitanyi, P.: An Introduction to Kolmogorov Complexity and Its Application, 2nd edn. Springer, Heidelberg (1997)

    Google Scholar 

  8. Li, S.-Y.R., Yeung, R.W., Cai, N.: Linear network coding. IEEE Transactions on Information Theory 49, 371–381 (2003)

    Article  MATH  MathSciNet  Google Scholar 

  9. Muchnik, A.: Conditional complexity and codes. Theoretical Computer Science 271(1–2), 91–109 (2002)

    Google Scholar 

  10. 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

    Google Scholar 

  11. 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)

    Google Scholar 

  12. 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)

    Google Scholar 

  13. 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

  14. Yeung, R.: A First Course in Information Theory. Springer, Heidelberg (2002)

    Google Scholar 

Download references

Author information

Authors and Affiliations

Authors

Editor information

Editors and Affiliations

Rights and permissions

Reprints 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)

Publish with us

Policies and ethics