Online Public Access Catalogue (OPAC)
Library,Documentation and Information Science Division

“A research journal serves that narrow

borderland which separates the known from the unknown”

-P.C.Mahalanobis


Kolmogorov complexity and algorithmic randomness /



xviii, 511 pages : illustrations ; 27 cm. - (Mathematical surveys and monographs ; v 220.) Content notes : Preface --
Basic notions and notation --
Introduction : What is this book about? --
1. Plain Kolmogorov complexity -
2. Complexity of pairs and conditional complexity --
3. Martin-Löf randomness --
4. A priori probability and prefix complexity --
5. Monotone complexity --
6. General scheme for complexities --
7. Shannon entropy and Kolmogorov complexity --
8. Some applications --
9. Frequency and game approaches to randomness --
10. Inequalities for entropy, complexity, and size --
11. Common information --
12. Multisource algorithmic information theory --
13. Information and logic --
14. Algorithmic statistics --
Appendix 1. Complexity and foundations of probability --
Appendix 2. Four algorithmic faces of randomness. Computational complexity. Information theory. Vereshchagin, N.,

Library, Documentation and Information Science Division, Indian Statistical Institute, 203 B T Road, Kolkata 700108, INDIA
Phone no. 91-33-2575 2100, Fax no. 91-33-2578 1412, ksatpathy@isical.ac.in