Information Theory and Kolmogorov Complexity Research

Universidade Federal de Pelotas - Brazil

Andrei Nikolaevich Kolmogorov

Staff

• Carlos A. P. Campani (UFPel - personal home page)
  
• Sérgio Cardoso de Oliveira (UFPel)
  
• Paulo Blauth Menezes (UFRGS - personal home page)

Tutorial

• CAMPANI, C. ; MENEZES, P. Introdução à Complexidade de Kolmogorov. (in portuguese)

Recent Publications on Information Theory and Kolmogorov Complexity

• CAMPANI, C. ; MENEZES, P. Teorias da Aleatoriedade. In: Revista de Informática Teórica e Aplicada, UFRGS, 2004, p. 75-98. (in portuguese)

• CAMPANI, C. ; MENEZES, P. On the Application of Kolmogorov Complexity to the Characterization and Evaluation of Computational Models and Complex Systems. In: CISST'2004: International Conference on Imaging Science, Systems and Technology, 2004, Las Vegas, Anais... CSREA Press, 2004. v.1, p. 63-68.

• CAMPANI, C. ; MENEZES, P. Evaluating Computer Animation Models with Lossy Data Compression Using Kolmogorov Complexity, In: H. R. Arabnia and Y. Mun, editors, Proceedings of the 2003 International Conference Imaging Science, Systems, and Technology (CISST'03), pages 721-725. CSREA Press, 2003.

• CAMPANI, C. ; MENEZES, P. Complexidade de Kolmogorov e Caracterização da Hierarquia de Classes de Linguagens Formais - Uma Introdução. In: 5th Workshop on Formal Methods, WMF'2002, oct. 15-16, 2002, Gramado, p. 68-83. (in portuguese)

• CAMPANI, C. ; MENEZES, P. Aplicação da Complexidade de Kolmogorov na Caracterização e Avaliação de Modelos Computacionais e Sistemas Complexos. In: 5th Workshop on Formal Methods, WMF'2002, oct. 15-16, 2002, Gramado, p. 100-112. (in portuguese)

• CAMPANI, C. ; MENEZES, P. Characterizing the Software Development Process: A New Approach Based on Kolmogorov Complexity. In: Computer Aided Systems Theory - EUROCAST'2001, 8th International Workshop on Computer Aided Systems Theory, Las Palmas de Gran Canaria, Spain, feb. 19-23, 2001, Lecture Notes in Computer Science, Springer, v. 2178, p. 242-256, 2001.
  (see also: © Springer, Lecture Notes in Computer Science)

• CAMPANI, C. ; MENEZES, P. Characterizing the Software Development Process: A New Approach Based on Kolmogorov Complexity. In: EUROCAST'2001, Formal Methods and Tools for Computer Science, Extended Abstracts, Las Palmas de Gran Canaria, Spain, feb. 19-23, 2001, p. 78-81.
  (extended abstract)

Selected Texts (Virtual Library)

• Kolmogorov Complexity: Sources, Theory and Applications, A. Gammerman and V. Vovk, The Computer Journal, 1999

• Kolmogorov Complexity and its Applications : lecture notes by Alexander Shen.

• Lecture notes on descriptional complexity and randomness, 1993, Peter Gács

• A Theory of Program Size Formally Identical to Information Theory, G. Chaitin, Journal of the ACM, 1975

• Algorithmic Information Theory, G. Chaitin, IBM J. of Research and Develop., 1977

• The Discovery of Algorithmic Probability, Ray Solomonoff

• Randomness. P.M.B. Vitanyi, In: `Matematica, Logica, Informatica' Volume 12 of the Storia del XX Secolo, to be published by the Instituto della Enciclopedia Italiana.

• A Mathematical Theory of Communication, Claude Shannon, 1948.

If any file in this page violates copyrights, please send an e-mail warning about it.

Additional Reading

• Kolmogorov, A. Three approaches to the quantitative definition of information. Problems of Information Transmission, v. 1, p. 4-7, 1965.

• Kolmogorov, A. Logical basis for information theory and probability theory. IEEE Transactions on Information Theory, v. 14, n. 5, p. 662-664, 1968.

• Martin-Löf, P. The definition of random sequences. Inform. Contr., v. 9, p. 602-619, 1966.

• Uspensky, V. and Semenov, A. and Shen A. Can an individual sequence of zeros and ones be random? Russian Math. Surveys, v. 45, n. 1, p. 121-189, 1990.

• Zvonkin, A. and Levin, L. The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms. Russian Math. Surveys, v. 25, n. 6, p. 83-124, 1970.

• Theoretical Computer Science, Volume 207, Issue 2, 6 November 1998.

• Theoretical Computer Science, Volume 271, Issue 1-2, 28 January 2002.

Recomended Books

• An Introduction to Kolmogorov Complexity and its Applications, M. Li and P.M.B. Vitanyi, Springer, 1997.

• The Limits of Mathematics, G. Chaitin, Springer.

• Elements of information Theory, Thomas Cover & Joy Thomas.

• Mathematical Foundations of Information Theory, A. Khinchin, Dover, 1957.

All books available at Amazon.com.

Links

• ACM: Association for Computing Machinery, the world's first educational and scientific computing society.
• Alan Turing Home Page
• arXiv.org e-Print archive
• Centre for Quantum Computation - Home Page
• ECCC - The Electronic Colloquium on Computational Complexity
• Entropy in Logic and the Theory of Algorithms
• Entropy on the World Wide Web
• G.J.Chaitin Home Page
• History of Mathematics
• IEEE Information Theory Society HOME Page
• IEEE.org
• Information Theory Resources
• Kolmogorov Complexity and Applications - Lecture Notes
• Kolmogorov Complexity Resources
• Ming Li's Home Page
• NEC ResearchIndex
• Paul Vitanyi
• Peter Gács
• Quantum Information and Computing
• Ray Solomonoff's Homepage
• The Collection of Computer Science Bibliographies
• The Computer Journal - Special Issue on Kolmogorov Complexity
• The Computer Science Preprint Server
• Professor Thomas M. Cover