The complexity of finite objects and the development of the concepts of information and randomness by means of the theory of algorithms
A. K. Zvonkin, L. A. Levin

This publication is cited in the following articles:

1. Huazheng Han, Xuejin Gao, Huayun Han, Huihui Gao, Yongsheng Qi, “Human-Like One-Shot Fault Diagnosis via Large Language Model”, IEEE Trans. Syst. Man Cybern, Syst., 56:2 (2026), 1038  
2. Laurent Bienvenu, Christopher P. Porter, “Bridging computational notions of depth”, Information and Computation, 2026, 105420  
3. Brani Vidakovic, “Adjusted Kolmogorov Complexity of Binary Words with Empirical Entropy Normalization”, Entropy, 28:2 (2026), 176  
4. Giulio Ruffini, “The Algorithmic Regulator”, Entropy, 28:3 (2026), 257  
5. Peter Gacs, Yuri Kalnishkan, Alexander Shen, Vladimir Vovk, “Vladimir V'yugin: short biography and some research contributions”, Information and Computation, 2026, 105429  
6. Shuichi Hirahara, Zhenjian Lu, Igor C. Oliveira, Lecture Notes in Computer Science, 15364, Theory of Cryptography, 2025, 253  
7. Neri Merhav, “Universal Slepian-Wolf Coding for Individual Sequences”, IEEE Trans. Inform. Theory, 71:1 (2025), 783  
8. Ming Li, “Caging AI”, J. Comput. Sci. Technol., 40:1 (2025), 1  
9. Michael Blank, “Are prime numbers and quadratic residues random?”, DCDS, 2025  
10. A. L. Semenov, M. A. Babenko, A. Ya. Belov, N. K. Vereshchagin, M. E. Vishnikin, E. E. Zolin, V. N. Krupski, S. L. Kuznetsov, V. A. Lyubetskii, A. A. Onoprienko, M. R. Pentus, S. F. Soprunov, A. A. Sorokin, V. B. Shehtman, T. L. Yavorskaya, “Chair of Mathematical Logic and Theory of Algorithms”, Moscow University Mathematics Bulletin, 80:1 (2025), 23–33        
11. Gert de Cooman, Floris Persiau, Jasper De Bock, “Randomness and imprecision: From supermartingales to randomness tests”, Information and Computation, 306 (2025), 105328  
12. Christoph Flamm, Daniel Merkle, Peter F. Stadler, “Assembly in Directed Hypergraphs”, Proc. R. Soc. A., 481:2324 (2025)  
13. V.V. V'yugin, “Kolmogorov complexity in the USSR (1975–1982): isolation and its end”, Information and Computation, 2025, 105374  
14. Kenshi Miyabe, “Randomness with respect to c.e. semimeasures”, Information and Computation, 2025, 105384  
15. Andrei Romashchenko, “Algebraic Barriers to Halving Algorithmic Information Quantities in Correlated Strings”, Information and Computation, 2025, 105396  
16. M. L. Blank, “Local dynamical entropies and their applications to number theory”, Theory Probab. Appl., 70:4 (2026), 516–539      
17. Mingyang Li, Jan Reimann, “Turing degrees and randomness for continuous measures”, Arch. Math. Logic, 63:1-2 (2024), 39  
18. Markus Pantsar, “Theorem proving in artificial neural networks: new frontiers in mathematical AI”, Euro Jnl Phil Sci, 14:1 (2024)  
19. Mariano Lemus, Ricardo Faleiro, Paulo Mateus, Nikola Paunković, André Souto, “Quantum Kolmogorov complexity and quantum correlations in deterministic-control quantum Turing machines”, Quantum, 8 (2024), 1230  
20. Emirhan Gürpιnar, Andrei Romashchenko, “Communication Complexity of the Secret Key Agreement in Algorithmic Information Theory”, ACM Trans. Comput. Theory, 2024  
21. Zoe Leyva-Acosta, Eduardo Acuña Yeomans, Francisco Hernandez-Quiroz, “An Additively Optimal Interpreter for Approximating Kolmogorov Prefix Complexity”, Entropy, 26:9 (2024), 802  
22. Shuichi Hirahara, Zhenjian Lu, Mikito Nanashima, 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), 2024, 369  
23. Geoffroy Caillat-Grenier, Andrei Romashchenko, Rustam Zyavgarov, 2024 IEEE Information Theory Workshop (ITW), 2024, 181  
24. Klaas Landsman, “Typical = Random”, Axioms, 12:8 (2023), 727  
25. Bruno Bauwens*, Marius Zimand, “Universal almost Optimal Compression and Slepian-wolf Coding in Probabilistic Polynomial Time”, J. ACM, 70:2 (2023), 1  
26. Shuichi Hirahara, Rahul Ilango, Zhenjian Lu, Mikito Nanashima, Igor C. Oliveira, Proceedings of the 55th Annual ACM Symposium on Theory of Computing, 2023, 1039  
27. George Barmpalias, Alexander Shen, “The Kučera–Gács theorem revisited by Levin”, Theoretical Computer Science, 947 (2023), 113693  
28. Laurent Beaudoin, Loïca Avanthey, “How to help digital-native students to successfully take control of their learning: A return of 8 years of experience on a computer science e-learning platform in higher education”, Educ Inf Technol, 28:5 (2023), 5421  
29. Yanyi Liu, Rafael Pass, Lecture Notes in Computer Science, 14082, Advances in Cryptology – CRYPTO 2023, 2023, 645  
30. Rahul Ilango, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 733  
31. Marshall Ball, Yanyi Liu, Noam Mazor, Rafael Pass, 2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), 2023, 458  
32. Adam Case, Christopher P. Porter, “The Intersection of Algorithmically Random Closed Sets and Effective Dimension”, ACM Trans. Comput. Logic, 23:4 (2022), 1  
33. Andrei Romashchenko, “Clustering with respect to the information distance”, Theoretical Computer Science, 929 (2022), 164  
34. Hansika Hewamalage, Christoph Bergmeir, Kasun Bandara, “Global models for time series forecasting: A Simulation study”, Pattern Recognition, 124 (2022), 108441  
35. Rafael Grompone von Gioi, Ignacio Ramírez Paulino, Gregory Randall, “The Whole and the Parts: The Minimum Description Length Principle and the A-Contrario Framework”, SIAM J. Imaging Sci., 15:3 (2022), 1282  
36. Leonid A. Levin, “Gacs – Kucera theorem”, Theoretical Computer Science, 929 (2022), 172  
37. Laurent Bienvenu, Glenn Shafer, Alexander Shen, Trends in the History of Science, The Splendors and Miseries of Martingales, 2022, 405  
38. Laurent Bienvenu, Glenn Shafer, Alexander Shen, Trends in the History of Science, The Splendors and Miseries of Martingales, 2022, 225  
39. Yu Liu, Zengru Di, Philip Gerlee, “Ladderpath Approach: How Tinkering and Reuse Increase Complexity and Information”, Entropy, 24:8 (2022), 1082  
40. Neil Lutz, “Fractal Intersections and Products via Algorithmic Dimension”, ACM Trans. Comput. Theory, 13:3 (2021), 1  
41. Samuel Epstein, “All Sampling Methods Produce Outliers”, IEEE Trans. Inform. Theory, 67:11 (2021), 7568  
42. Shuichi Hirahara, Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021, 292  
43. Yanyi Liu, Rafael Pass, Lecture Notes in Computer Science, 12825, Advances in Cryptology – CRYPTO 2021, 2021, 11  
44. Klaas Landsman, The Frontiers Collection, Undecidability, Uncomputability, and Unpredictability, 2021, 17  
45. Aliyu Sani Sambo, R. Muhammad Atif Azad, Yevgeniya Kovalchuk, Vivek Padmanaabhan Indramohan, Hanifa Shah, “Evolving simple and accurate symbolic regression models via asynchronous parallel computing”, Applied Soft Computing, 104 (2021), 107198  
46. A.I. Vlasov, L.V. Zhuravleva, V.V. Kazakov, “Methods for Formalizing Cognitive Graphics and Visual Models using XML Schemas”, HoBMSTU.SIE, 2021, no. 1 (134), 51  
47. Information Theory Meets Power Laws, 2020, 351  
48. Daniil Ryabko, SpringerBriefs in Computer Science, Universal Time-Series Forecasting with Mixture Predictors, 2020, 1  
49. Eiji Konishi, “Holographic interpretation of Shannon entropy of coherence of quantum pure states”, EPL, 129:1 (2020), 11006  
50. Markus P. Müller, “Law without law: from observer states to physics via algorithmic information theory”, Quantum, 4 (2020), 301  
51. Daniil Ryabko, SpringerBriefs in Computer Science, Universal Time-Series Forecasting with Mixture Predictors, 2020, 17  
52. Morgane Austern, Arian Maleki, “On the Gaussianity of Kolmogorov Complexity of Mixing Sequences”, IEEE Trans. Inform. Theory, 66:2 (2020), 1232  
53. Paul M.B. Vitányi, “How Incomputable Is Kolmogorov Complexity?”, Entropy, 22:4 (2020), 408  
54. Christopher P Porter, “Effective aspects of Bernoulli randomness”, Journal of Logic and Computation, 29:6 (2019), 933  
55. Samuel Epstein, “Algorithmic No-Cloning Theorem”, IEEE Trans. Inform. Theory, 65:9 (2019), 5925  
56. Tom F. Sterkenburg, “Putnam's Diagonal Argument and the Impossibility of a Universal Learning Machine”, Erkenn, 84:3 (2019), 633  
57. Matthew Harrison-Trainor, Bakh Khoussainov, Daniel Turetsky, Vasco Brattka, Rod Downey, Julia F. Knight, Steffen Lempp, “Effective aspects of algorithmically random structures”, COM, 8:3-4 (2019), 359  
58. Andrei Romashchenko, Marius Zimand, “An Operational Characterization of Mutual Information in Algorithmic Information Theory”, J. ACM, 66:5 (2019), 1  
59. Xiang Huang, Jack H. Lutz, Andrei N. Migunov, 2019 57th Annual Allerton Conference on Communication, Control, and Computing (Allerton), 2019, 615  
60. Rodrick Wallace, SpringerBriefs in Applied Sciences and Technology, Carl von Clausewitz, the Fog-of-War, and the AI Revolution, 2018, 47  
61. Sean Devine, “An Economy Viewed as a Far-from-Equilibrium System from the Perspective of Algorithmic Information Theory”, Entropy, 20:4 (2018), 228  
62. A. N. Gorban, “Hilbert's sixth problem: the endless road to rigour”, Phil. Trans. R. Soc. A., 376:2118 (2018), 20170238  
63. Daniel Vogler, Sassan Ostvar, Rebecca Paustian, Brian D. Wood, “A hierarchy of models for simulating experimental results from a 3D heterogeneous porous medium”, Advances in Water Resources, 114 (2018), 149  
64. Rodrick Wallace, “New statistical models of nonergodic cognitive systems and their pathologies”, Journal of Theoretical Biology, 436 (2018), 72  
65. Samad Khabbazi Oskouei, Stefano Mancini, “Algorithmic complexity of quantum capacity”, Quantum Inf Process, 17:4 (2018)  
66. Birzhan Moldagaliyev, Ludwig Staiger, Frank Stephan, Lecture Notes in Computer Science, 10977, Implementation and Application of Automata, 2018, 274  
67. Hamid Akin Unver, “Computational International Relations: What Can Programming, Coding and Internet Research Do for the Discipline?”, SSRN Journal, 2018  
68. Sean Devine, “Algorithmic Entropy and Landauer's Principle Link Microscopic System Behaviour to the Thermodynamic Entropy”, Entropy, 20:10 (2018), 798  
69. Lin Ma, Jean-Paul Delahaye, “An Algorithmic Look at Financial Volatility”, Algorithms, 11:11 (2018), 185  
70. Laurent Bienvenu, Mathieu Hoyrup, Alexander Shen, “Layerwise Computability and Image Randomness”, Theory Comput Syst, 61:4 (2017), 1353  
71. Tom F. Sterkenburg, “A Generalized Characterization of Algorithmic Probability”, Theory Comput Syst, 61:4 (2017), 1337  
72. Charlotte Fiskum, Tonje Grønning Andersen, Per M. Aslaksen, Birgit Svendsen, Magne A. Flaten, Karl Jacobsen, “Cardiac complexity and emotional dysregulation in children”, International Journal of Psychophysiology, 121 (2017), 38  
73. Robert C. Whetsel, Yanzhen Qu, 2017 3rd IEEE International Conference on Computer and Communications (ICCC), 2017, 2299  
74. Jan Reimann, Frank Stephan, Logic Colloquium '01, 2017, 369  
75. Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter, Paul Shafer, “Randomness and Semimeasures”, Notre Dame J. Formal Logic, 58:3 (2017)  
76. Scott Garrabrant, Tsvi Benson-Tilsen, Andrew Critch, Nate Soares, Jessica Taylor, “A Formal Approach to the Problem of Logical Non-Omniscience”, Electron. Proc. Theor. Comput. Sci., 251 (2017), 221  
77. F. Benatti, S. Khabbazi Oskouei, A. Shafiei Deh Abad, “Quantum Entropy and Complexity”, Open Syst. Inf. Dyn., 24:02 (2017), 1750005  
78. Jaime A. Londoño, “An Approach of Randomness of a Sample Based on Its Weak Ergodic Limit”, Journal of Probability and Statistics, 2017 (2017), 1  
79. J. Math. Sci. (N. Y.), 226:5 (2017), 667–693      
80. Cristian S. Calude, Ludwig Staiger, Frank Stephan, “Finite state incompressible infinite sequences”, Information and Computation, 247 (2016), 23  
81. Martin Hilbert, “Formal definitions of information and knowledge and their role in growth through structural change”, Structural Change and Economic Dynamics, 38 (2016), 69  
82. Bakhadyr Khoussainov, Lecture Notes in Computer Science, 9537, Logical Foundations of Computer Science, 2016, 159  
83. Domenico Maisto, Francesco Donnarumma, Giovanni Pezzulo, “Nonparametric Problem-Space Clustering: Learning Efficient Codes for Cognitive Control Tasks”, Entropy, 18:2 (2016), 61  
84. Jason Teutsch, Marius Zimand, “A Brief on Short Descriptions”, SIGACT News, 47:1 (2016), 42  
85. Sebastiaan A. Terwijn, The Frontiers Collection, The Challenge of Chance, 2016, 49  
86. Sean D. Devine, “Understanding how replication processes can maintain systems away from equilibrium using Algorithmic Information Theory”, Biosystems, 140 (2016), 8  
87. Tom F. Sterkenburg, “Solomonoff Prediction and Occam's Razor”, Philos. of Sci., 83:4 (2016), 459  
88. Sanjay Jain, Frank Stephan, Jason Teutsch, “Closed left-r.e. sets”, COM, 6:1 (2016), 1  
89. Daniil Ryabko, Lecture Notes in Computer Science, 9925, Algorithmic Learning Theory, 2016, 253  
90. Mikhail Andreev, Akim Kumok, “The Sum 2 KM(x)−K(x) Over All Prefixes x of Some Binary Sequence Can be Infinite”, Theory Comput Syst, 2015  
91. Winston Ewert, William A. Dembski, Robert J. Marks, “Measuring meaningful information in images: algorithmic specified complexity”, IET Computer Vision, 9:6 (2015), 884  
92. Jason Teutsch, Marius Zimand, “On Approximate Decidability of Minimal Programs”, ACM Trans. Comput. Theory, 7:4 (2015), 1  
93. Martin Hilbert, 2015 48th Hawaii International Conference on System Sciences, 2015, 3841  
94. Andrew R. Cohen, Paul M.B. Vitanyi, “Normalized Compression Distance of Multisets with Applications”, IEEE Trans. Pattern Anal. Mach. Intell., 37:8 (2015), 1602  
95. Yuri I. Manin, Emergence, Complexity and Computation, 14, ISCS 2014: Interdisciplinary Symposium on Complex Systems, 2015, 3  
96. Yuri Kalnishkan, Measures of Complexity, 2015, 117  
97. Frank Stephan, Jason Teutsch, “Things that can be made into themselves”, Information and Computation, 2014  
98. Kenshi Miyabe, “Algorithmic randomness over general spaces”, Math. Log. Quart, 60:3 (2014), 184  
99. Jason Teutsch, “Short lists for shortest descriptions in short time”, comput. complex, 2014  
100. Yu. I. Manin, “Zipf's Law and L. Levin Probability Distributions”, Funct. Anal. Appl., 48:2 (2014), 116–127              
101. Tor Lattimore, Marcus Hutter, “On Martin-Löf (non-)convergence of Solomonoff's universal mixture”, Theoretical Computer Science, 2014  
102. Manin Y.I., “Complexity Vs Energy: Theory of Computation and Theoretical Physics”, 3Quantum: Algebra Geometry Information, Journal of Physics Conference Series, 532, IOP Publishing Ltd, 2014, 012018    
103. Manin Yu., Marcolli M., “Kolmogorov Complexity and the Asymptotic Bound For Error-Correcting Codes”, J. Differ. Geom., 97:1 (2014), 91–108  
104. Ferit Toska, “Strict process machine complexity”, Arch. Math. Logic, 53:5-6 (2014), 525  
105. Laurent Orseau, Lecture Notes in Computer Science, 8598, Artificial General Intelligence, 2014, 97  
106. B. BAUWENS, A. SHEN, “COMPLEXITY OF COMPLEXITY AND STRINGS WITH MAXIMAL PLAIN AND PREFIX KOLMOGOROV COMPLEXITY”, J. symb. log., 79:2 (2014), 620  
107. Bakhadyr Khoussainov, Proceedings of the Joint Meeting of the Twenty-Third EACSL Annual Conference on Computer Science Logic (CSL) and the Twenty-Ninth Annual ACM/IEEE Symposium on Logic in Computer Science (LICS), 2014, 1  
108. Peter Gács, Wiley StatsRef: Statistics Reference Online, 2014  
109. Bruno Bauwens, Marius Zimand, 2014 IEEE 29th Conference on Computational Complexity (CCC), 2014, 241  
110. Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, Florian Speelman, Proceedings of the forty-sixth annual ACM symposium on Theory of computing, 2014, 857  
111. Laurent Orseau, Lecture Notes in Computer Science, 8598, Artificial General Intelligence, 2014, 109  
112. Marie Ferbus-Zanda, Serge Grigorieff, Logic, Epistemology, and the Unity of Science, 34, Constructivity and Computability in Historical and Philosophical Perspective, 2014, 57  
113. José Hernández-Orallo, David L. Dowe, “On Potential Cognitive Abilities in the Machine Kingdom”, Minds & Machines, 2013  
114. Sergio Romano, Mariano Sigman, Santiago Figueira, “$LT^2C^2$ : A language of thought with Turing-computable Kolmogorov complexity”, Pap. Phys, 5 (2013)  
115. Dusko Pavlovic, “Monoidal computer I: Basic computability by string diagrams”, Information and Computation, 2013  
116. EIJI KONISHI, “TIME AND A TEMPORALLY STATISTICAL QUANTUM GEOMETRODYNAMICS”, Int. J. Mod. Phys. A, 2013, 1330015  
117. P.M..B. Vitányi, “Conditional Kolmogorov complexity and universal probability”, Theoretical Computer Science, 2013  
118. Nicolas Gauvrit, Hector Zenil, Jean-Paul Delahaye, Fernando Soler-Toscano, “Algorithmic complexity for short binary strings applied to psychology: a primer”, Behav Res, 2013  
119. Dusko Pavlovic, Lecture Notes in Computer Science, 7860, Computation, Logic, Games, and Quantum Foundations. The Many Facets of Samson Abramsky, 2013, 291  
120. Wolfgang Merkle, Frank Stephan, Jason Teutsch, Wei Wang, Yue Yang, Lecture Notes in Computer Science, 7876, Theory and Applications of Models of Computation, 2013, 144  
121. Yoshitsugu Oono, Springer Series in Synergetics, The Nonlinear World, 2013, 35  
122. Tarik Kaced, Andrei Romashchenko, “Conditional Information Inequalities for Entropic and Almost Entropic Points”, IEEE Trans. Inform. Theory, 59:11 (2013), 7149  
123. Leonid A. Levin, “Forbidden information”, J. ACM, 60:2 (2013), 1  
124. Alexei Grinbaum, New Challenges to Philosophy of Science, 2013, 59  
125. Ian Wood, Peter Sunehag, Marcus Hutter, Lecture Notes in Computer Science, 7070, Algorithmic Probability and Friends. Bayesian Prediction and Artificial Intelligence, 2013, 417  
126. Tor Lattimore, Marcus Hutter, Lecture Notes in Computer Science, 7876, Theory and Applications of Models of Computation, 2013, 212  
127. Martin Hilbert, “Linking Information, Knowledge and Evolutionary Growth: A Multilevel Interplay between Natural Selection and Informed Intervention”, SSRN Journal, 2013  
128. S. Nath, R. Venkatesan, 2013 IEEE 29th International Conference on Data Engineering (ICDE), 2013, 517  
129. Verónica Becher, Pablo Ariel Heiber, “A linearly computable measure of string complexity”, Theoretical Computer Science, 2012  
130. Boris Ryabko, Zhanna Reznikova, Alexey Druzyaka, Sofia Panteleeva, “Using Ideas of Kolmogorov Complexity for Studying Biological Texts”, Theory Comput Syst, 2012  
131. Adam R. Day, “Process and truth-table characterisations of randomness”, Theoretical Computer Science, 2012  
132. Luís Antunes, Armando Matos, Alexandre Pinto, André Souto, Andreia Teixeira, “One-Way Functions Using Algorithmic and Classical Information Theories”, Theory Comput Syst, 2012  
133. EIJI KONISHI, “MODELING QUANTUM MECHANICAL OBSERVERS VIA NEURAL-GLIAL NETWORKS”, Int. J. Mod. Phys. B, 26:09 (2012), 1250060  
134. Frank Stephan, Jason Teutsch, “An incomplete set of shortest descriptions”, J. symb. log, 77:01 (2012), 291  
135. Cezar Câmpeanu, Lecture Notes in Computer Science, 7160, Computation, Physics and Beyond, 2012, 71  
136. Hector Zenil, Lecture Notes in Computer Science, 7160, Computation, Physics and Beyond, 2012, 224  
137. Laurent Orseau, Mark Ring, Lecture Notes in Computer Science, 7716, Artificial General Intelligence, 2012, 219  
138. Bjørn Kjos-Hanssen, Frank Stephan, Jason Teutsch, “Arithmetic complexity via effective names for random sequences”, ACM Trans. Comput. Logic, 13:3 (2012), 1  
139. Laurent Orseau, Mark Ring, Lecture Notes in Computer Science, 7716, Artificial General Intelligence, 2012, 209  
140. Alexandr Kirillov, Sergey Kirillov, Michael Pecht, Proceedings of the IEEE 2012 Prognostics and System Health Management Conference (PHM-2012 Beijing), 2012, 1  
141. Marius Zimand, Lecture Notes in Computer Science, 7160, Computation, Physics and Beyond, 2012, 241  
142. Bruno Bauwens, Lecture Notes in Computer Science, 7391, Automata, Languages, and Programming, 2012, 100  
143. Leonid A. Levin, 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, 2012, 510  
144. K. Vela Velupillai, Nonlinearity, Complexity and Randomness in Economics, 2012, 151  
145. A Level of Martin-Lof Randomness, 2012, 88  
146. K. Vela Velupillai, “NON-LINEAR DYNAMICS, COMPLEXITY AND RANDOMNESS: ALGORITHMIC FOUNDATIONS”, Journal of Economic Surveys, 2011, no  
147. V. V. V'yugin, “On universal algorithms for adaptive forecasting”, Problems Inform. Transmission, 47:2 (2011), 166–189        
148. Gerard Briscoe, Philippe De Wilde, “Physical complexity of variable length symbolic sequences”, Physica A: Statistical Mechanics and its Applications, 2011  
149. Paul E Rapp, Christopher J Cellucci, Adele MK Gilpin, Miguel A Jiménez-Montaño, Kathryn E Korslund, “Communication patterns in a psychotherapy following traumatic brain injury: A quantitative case study based on symbolic dynamics”, BMC Psychiatry, 11:1 (2011), 119  
150. Kohtaro Tadaki, “A Chaitin
     $$\Upomega$$
     number based on compressible strings”, Nat Comput, 2011  
151. Joseph S. Miller, Liang Yu, “Oscillation in the initial segment complexity of random reals”, Advances in Mathematics, 226:6 (2011), 4816  
152. Nikolay K. Vereshchagin, Andrej A. Muchnik, “On joint conditional complexity (entropy)”, Proc. Steklov Inst. Math., 274 (2011), 90–104            
153. Laurent Bienvenu, Peter Gács, Mathieu Hoyrup, Cristobal Rojas, Alexander Shen, “Algorithmic tests and randomness with respect to a class of measures”, Proc. Steklov Inst. Math., 274 (2011), 34–89            
154. James P. Crutchfield, “Between order and chaos”, Nat Phys, 8:1 (2011), 17  
155. M. Zimand, “Generating Kolmogorov random strings from sources with limited independence”, Journal of Logic and Computation, 2011  
156. Sebastiaan A. Terwijn, Leen Torenvliet, Paul M.B. Vitányi, “Nonapproximability of the normalized information distance”, Journal of Computer and System Sciences, 77:4 (2011), 738  
157. Uspensky V.A., V'yugin V.V., “Development of the algorithmic information theory in Russia”, Journal of Communications Technology and Electronics, 56:6 (2011), 739–747    
158. Gidlevskii A.V., “Paradoksy entropii (spekulyativnyi kharakter sovremennoi nauchnoi metodologii)”, Vestnik omskogo universiteta, 2011, no. 4, 199–201  
159. Paul M. B. Vitanyi, “Information Distance in Multiples”, IEEE Trans. Inform. Theory, 57:4 (2011), 2451  
160. Daniil Musatov, Lecture Notes in Computer Science, 6651, Computer Science – Theory and Applications, 2011, 64  
161. Marcus Hutter, Encyclopedia of Machine Learning, 2011, 1001  
162. Sanjay Jain, Frank Stephan, Jason Teutsch, Lecture Notes in Computer Science, 6648, Theory and Applications of Models of Computation, 2011, 218  
163. Tarik Kaced, Andrei Romashchenko, 2011 IEEE International Symposium on Information Theory Proceedings, 2011, 1935  
164. D Abel, Models and Applications of Chaos Theory in Modern Sciences, 2011, 123  
165. Tor Lattimore, Marcus Hutter, Vaibhav Gavane, Lecture Notes in Computer Science, 6925, Algorithmic Learning Theory, 2011, 262  
166. Dusko Pavlovic, Proceedings of the 2011 New Security Paradigms Workshop, 2011, 125  
167. Marius Zimand, 2011 IEEE 26th Annual Conference on Computational Complexity, 2011, 148  
168. Alexandr Kirillov, Olga Kirillova, Sergey Kirillov, 2011 3rd International Conference on Advanced Computer Control, 2011, 138  
169. Tarik Kaced, 2011 IEEE International Symposium on Information Theory Proceedings, 2011, 1603  
170. Sergey Kirillov, Aleksander Kirillov Sr, Olga Kirillova, SAE Technical Paper Series, 1, SAE Technical Paper Series, 2011  
171. An. A. Muchnik, A. E. Romashchenko, “Stability of properties of Kolmogorov complexity under relativization”, Problems Inform. Transmission, 46:1 (2010), 38–61          
172. Matilde Marcolli, Yuri I. Manin, “Error-Correcting Codes and Phase Transitions”, Math comput sci, 2010  
173. Peter Gács, Mathieu Hoyrup, Cristóbal Rojas, “Randomness on Computable Probability Spaces—A Dynamical Point of View”, Theory Comput Systems, 2010  
174. Jürgen Schmidhuber, “The new AI is general and mathematically rigorous”, Front Electr Electron Eng China, 2010  
175. Vladimir V’yugin, “On Empirical Meaning of Randomness with Respect to Parametric Families of Probability Distributions”, Theory Comput Systems, 2010  
176. Cristian S. Calude, Marius Zimand, “Algorithmically independent sequences”, Information and Computation, 208:3 (2010), 292  
177. Markus Müller, “Stationary algorithmic probability”, Theoretical Computer Science, 411:1 (2010), 113  
178. Marius Zimand, Lecture Notes in Computer Science, 6281, Mathematical Foundations of Computer Science 2010, 2010, 701  
179. Marius Zimand, Lecture Notes in Computer Science, 6281, Mathematical Foundations of Computer Science 2010, 2010, 689  
180. George Barmpalias, “Relative Randomness and Cardinality”, Notre Dame J. Formal Logic, 51:2 (2010)  
181. Paul M.B. Vitanyi, “Ray Solomonoff, Founding Father of Algorithmic Information Theory”, Algorithms, 3:3 (2010), 260  
182. Lane A. Hemaspaandra, “SIGACT news complexity theory column 68”, SIGACT News, 41:4 (2010), 73  
183. Pavel Karpovich, Lecture Notes in Computer Science, 6072, Computer Science – Theory and Applications, 2010, 266  
184. Kohtaro Tadaki, 2010 IEEE Information Theory Workshop, 2010, 1  
185. Paul M.B. Vitanyi, “Ray Solomonoff, Founding Father of Algorithmic Information Theory”, Algorithms, 3:3 (2010), 260  
186. CRISTIAN S. CALUDE, LUDWIG STAIGER, “On universal computably enumerable prefix codes”, Math Struct Comp Sci, 19:1 (2009), 45        
187. Laurent Bienvenu, Andrej Muchnik, Alexander Shen, Nikolay Vereshchagin, “Limit Complexities Revisited”, Theory Comput Systems, 2009  
188. A. Yu. Kolesov, N. Kh. Rozov, “On the definition of ‘chaos’”, Russian Math. Surveys, 64:4 (2009), 701–744                  
189. Laurent Bienvenu, “Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity”, Theory Comput Systems, 2009    
190. Mathieu Hoyrup, Cristóbal Rojas, “Computability of probability measures and Martin-Löf randomness over metric spaces”, Information and Computation, 207:7 (2009), 830  
191. Vladimir V. V’yugin, “On calibration error of randomized forecasting algorithms”, Theoretical Computer Science, 410:19 (2009), 1781  
192. M.M. Hassan Mahmud, “On universal transfer learning”, Theoretical Computer Science, 410:19 (2009), 1826  
193. Fabio Benatti, “Quantum Algorithmic Complexities and Entropy”, Open Syst. Inf. Dyn, 16:01 (2009), 1  
194. D.L.. Abel, “The Capabilities of Chaos and Complexity”, IJMS, 10:1 (2009), 247  
195. Mathieu Hoyrup, Cristóbal Rojas, Lecture Notes in Computer Science, 5635, Mathematical Theory and Computational Practice, 2009, 260  
196. Mathieu Hoyrup, Cristóbal Rojas, Lecture Notes in Computer Science, 5555, Automata, Languages and Programming, 2009, 549  
197. Elva Diaz, Eunice Ponce-de-Leon, Pedro Larrañaga, Concha Bielza, Lecture Notes in Computer Science, 5845, MICAI 2009: Advances in Artificial Intelligence, 2009, 225  
198. Marcus Hutter, “Open Problems in Universal Induction & Intelligence”, Algorithms, 2:3 (2009), 879  
199. Marius Zimand, Lecture Notes in Computer Science, 5635, Mathematical Theory and Computational Practice, 2009, 499  
200. Kohtaro Tadaki, Lecture Notes in Computer Science, 5734, Mathematical Foundations of Computer Science 2009, 2009, 687  
201. Sean Devine, “The Insights of Algorithmic Entropy”, Entropy, 11:1 (2009), 85  
202. Michael G. Sadovsky, Julia A. Putintseva, Alexander S. Shchepanovsky, “Genes, information and sense: complexity and knowledge retrieval”, Theory Biosci, 127:2 (2008), 69        
203. J. Math. Sci. (N. Y.), 158:6 (2009), 787–808      
204. Daniil Ryabko, Marcus Hutter, “Predicting non-stationary processes”, Applied Mathematics Letters, 21:5 (2008), 477  
205. Hayato Takahashi, “On a definition of random sequences with respect to conditional probability”, Information and Computation, 206:12 (2008), 1375  
206. Jöran Mielke, “Refined Bounds on Kolmogorov Complexity for ω-Languages”, Electronic Notes in Theoretical Computer Science, 221 (2008), 181  
207. Ludwig Staiger, “On Oscillation-free ε-random Sequences”, Electronic Notes in Theoretical Computer Science, 221 (2008), 287  
208. Elvira Mayordomo, New Computational Paradigms, 2008, 259  
209. Victor Korotkich, Encyclopedia of Optimization, 2008, 1790  
210. Cristian S. Calude, Marius Zimand, Lecture Notes in Computer Science, 5257, Developments in Language Theory, 2008, 183  
211. Kohtaro Tadaki, 2008 IEEE International Symposium on Information Theory, 2008, 2111  
212. Andrei Muchnik, Andrei Romashchenko, Lecture Notes in Computer Science, 5162, Mathematical Foundations of Computer Science 2008, 2008, 527  
213. Vladimir V. V'yugin, Lecture Notes in Computer Science, 5010, Computer Science – Theory and Applications, 2008, 302  
214. David Doty, “Dimension Extractors and Optimal Decompression”, Theory Comput Systems, 2007      
215. John M. Hitchcock, María López-Valdés, Elvira Mayordomo, “Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets”, Theory Comput Systems, 2007    
216. Khushboo Shah, Edmond Jonckheere, Stephan Bohacek, “Dynamic Modeling of Internet Traffic for Intrusion Detection”, EURASIP J Adv Signal Process, 2007 (2007), 1    
217. Sheng-Tzong Cheng, Ming-Hung Tao, “Quantum cooperative search algorithm for 3-SAT”, Journal of Computer and System Sciences, 73:1 (2007), 123  
218. Nick Chater, Paul Vitányi, “‘Ideal learning’ of natural language: Positive results about learning from positive evidence”, Journal of Mathematical Psychology, 51:3 (2007), 135  
219. Alexey Chernov, Marcus Hutter, Jürgen Schmidhuber, “Algorithmic complexity bounds on future prediction errors”, Information and Computation, 205:2 (2007), 242  
220. Marcus Hutter, Andrej Muchnik, “On semimeasures predicting Martin-Löf random sequences”, Theoretical Computer Science, 382:3 (2007), 247  
221. Marcus Hutter, “On universal prediction and Bayesian confirmation”, Theoretical Computer Science, 384:1 (2007), 33  
222. Ludwig Staiger, “The Kolmogorov complexity of infinite words”, Theoretical Computer Science, 383:2-3 (2007), 187  
223. Sylvain Perifel, Lecture Notes in Computer Science, 4649, Computer Science – Theory and Applications, 2007, 315  
224. Bruno Durand, Alexander Zvonkin, Kolmogorov's Heritage in Mathematics, 2007, 281  
225. Socratic Epistemology, 2007, 189  
226. Jürgen Schmidhuber, Cognitive Technologies, Artificial General Intelligence, 2007, 175  
227. Vladimir V'yugin, Lecture Notes in Computer Science, 4649, Computer Science – Theory and Applications, 2007, 387  
228. Vladimir V. V'yugin, Lecture Notes in Computer Science, 4754, Algorithmic Learning Theory, 2007, 388  
229. Daniil Ryabko, Marcus Hutter, 2007 IEEE International Symposium on Information Theory, 2007, 2346  
230. M. M. Hassan Mahmud, Lecture Notes in Computer Science, 4754, Algorithmic Learning Theory, 2007, 135  
231. Fabio Benatti, Tyll Krüger, Markus Müller, Rainer Siegmund-Schultze, Arleta Szkoła, “Entropy and Quantum Kolmogorov Complexity: A Quantum Brudno’s Theorem”, Comm Math Phys, 265:2 (2006), 437        
232. Kohtaro Tadaki, “An extension of Chaitin's halting probability Ω to a measurement operator in an infinite dimensional quantum system”, MLQ - Math Log Quart, 52:5 (2006), 419        
233. Sean Devine, “The application of algorithmic information theory to noisy patterned strings”, Complexity, 12:2 (2006), 52      
234. Jan Poland, Marcus Hutter, “MDL convergence speed for Bernoulli sequences”, Stat Comput, 16:2 (2006), 161      
235. Marcus Hutter, “Sequential predictions based on algorithmic complexity”, Journal of Computer and System Sciences, 72:1 (2006), 95  
236. Marcus Hutter, “On generalized computable universal priors and their convergence”, Theoretical Computer Science, 364:1 (2006), 27  
237. Andrej Muchnik, Alexei Semenov, “Effective bounds for convergence, descriptive complexity, and natural examples of simple and hypersimple sets”, Annals of Pure and Applied Logic, 141:3 (2006), 437  
238. Rod Downey, D.R.. Hirschfeldt, André Nies, S.A.. Terwijn, “Calibrating Randomness”, Bull. symb. log, 12:03 (2006), 411  
239. Richard Beigel, Harry Buhrman, Peter Fejer, Lance Fortnow, Piotr Grabowski, “Enumerations of the Kolmogorov function”, J. symb. log, 71:02 (2006), 501  
240. Marcus Hutter, Lecture Notes in Computer Science, 3959, Theory and Applications of Models of Computation, 2006, 408  
241. Maria Lopez-Valdes, Lecture Notes in Computer Science, 4162, Mathematical Foundations of Computer Science 2006, 2006, 693  
242. Lance Fortnow, Troy Lee, Nikolai Vereshchagin, Lecture Notes in Computer Science, 3884, STACS 2006, 2006, 137  
243. J. Poland, M. Hutter, “Asymptotics of Discrete MDL for Online Prediction”, IEEE Trans Inform Theory, 51:11 (2005), 3780      
244. Jack H. Lutz, “Effective fractal dimensions”, MLQ - Math Log Quart, 51:1 (2005), 62        
245. B. Ya. Ryabko, V. A. Monarev, “Experimental Investigation of Forecasting Methods Based on Data Compression Algorithms”, Problems Inform. Transmission, 41:1 (2005), 65–69        
246. Michael V. Vyugin, Vladimir V. V’yugin, “Predictive complexity and information”, Journal of Computer and System Sciences, 70:4 (2005), 539  
247. Yuri Kalnishkan, Vladimir Vovk, Michael V. Vyugin, “How many strings are easy to predict?”, Information and Computation, 201:1 (2005), 55  
248. Troy Lee, Andrei Romashchenko, “Resource bounded symmetry of information revisited”, Theoretical Computer Science, 345:2-3 (2005), 386  
249. Peter Gács, “Uniform test of algorithmic randomness over a general space”, Theoretical Computer Science, 341:1-3 (2005), 91  
250. Ludwig Staiger, “Constructive dimension equals Kolmogorov complexity”, Information Processing Letters, 93:3 (2005), 149  
251. Daniil Ryabko, Lecture Notes in Computer Science, 3734, Algorithmic Learning Theory, 2005, 148  
252. Verónica Becher, Santiago Figueira, André Nies, Silvana Picchi, “Program Size Complexity for Possibly Infinite Computations”, Notre Dame J. Formal Logic, 46:1 (2005)  
253. David Doty, Xiaoyang Gu, Jack H. Lutz, Elvira Mayordomo, Philippe Moser, Lecture Notes in Computer Science, 3618, Mathematical Foundations of Computer Science 2005, 2005, 283  
254. Peter Gács, Encyclopedia of Statistical Sciences, 2005  
255. H. Takahashi, IEEE Information Theory Workshop, 2005., 2005, 4 pp.  
256. Alexey Chernov, Marcus Hutter, Lecture Notes in Computer Science, 3734, Algorithmic Learning Theory, 2005, 414  
257. H. Takahashi, “Redundancy of Universal Coding, Kolmogorov Complexity, and Hausdorff Dimension”, IEEE Trans Inform Theory, 50:11 (2004), 2727        
258. A. Yu. Khrennikov, Sh. Yamada, “On the concept of random sequence with respect to $p$-adic valued probabilities”, Theory Probab. Appl., 49:1 (2005), 65–76            
259. Rod G. Downey, Denis R. Hirschfeldt, Geoff LaForte, “Randomness and reducibility”, Journal of Computer and System Sciences, 68:1 (2004), 96  
260. Mark Burgin, “Algorithmic complexity of recursive and inductive algorithms”, Theoretical Computer Science, 317:1-3 (2004), 31  
261. Jan Poland, “A coding theorem for Enumerable Output Machines”, Information Processing Letters, 91:4 (2004), 157  
262. Liang Yu, Decheng Ding, Rodney Downey, “The Kolmogorov complexity of random reals”, Annals of Pure and Applied Logic, 129:1-3 (2004), 163  
263. Lowe B., Piwinger B., Rasch T., “Classical and New Paradigms of Computation and their Complexity Hierarchies - Papers of the Conference “Foundations of the Formal Sciences III{””, Classical and New Paradigms of Computation and their Complexity Hierarchies, Trends in Logic Studia Logica Library, 23, eds. Lowe B., Piwinger B., Rasch T., Springer, 2004, VII+  
264. Jan Poland, Marcus Hutter, Lecture Notes in Computer Science, 3244, Algorithmic Learning Theory, 2004, 294  
265. Rod Downey, Lecture Notes in Computer Science, 3153, Mathematical Foundations of Computer Science 2004, 2004, 42  
266. Jan Poland, Marcus Hutter, Lecture Notes in Computer Science, 3120, Learning Theory, 2004, 300  
267. Troy Lee, Andrei Romashchenko, Lecture Notes in Computer Science, 3153, Mathematical Foundations of Computer Science 2004, 2004, 463  
268. Yuri Kalnishkan, Vladimir Vovk, Michael V. Vyugin, Lecture Notes in Computer Science, 3244, Algorithmic Learning Theory, 2004, 249  
269. Marcus Hutter, Andrej Muchnik, Lecture Notes in Computer Science, 3244, Algorithmic Learning Theory, 2004, 234  
270. Rod Downey, Evan Griffiths, Geoffrey Laforte, “On Schnorr and computable randomness, martingales, and machines”, Mathematical Logic Qtrly, 50:6 (2004), 613  
271. Marcus Hutter, “Optimality of Universal Bayesian Sequence Prediction for General Loss and Alphabet”, J Machine Learning Res, 4:6 (2003), 971      
272. D.M. Sow, A. Eleftheriadis, “Complexity distortion theory”, IEEE Trans Inform Theory, 49:3 (2003), 604          
273. V. V. V'yugin, “Problems of Robustness for Universal Coding Schemes”, Problems Inform. Transmission, 39:1 (2003), 32–46        
274. L. A. Levin, “One-Way Functions”, Problems Inform. Transmission, 39:1 (2003), 92–103        
275. A. E. Romashchenko, “A Criterion of Extractability of the Mutual Information for a Triple of Strings”, Problems Inform. Transmission, 39:1 (2003), 148–157        
276. Peter Hertling, Klaus Weihrauch, “Random elements in effective topological spaces with measure”, Information and Computation, 181:1 (2003), 32  
277. Jack H. Lutz, “The dimensions of individual strings and sequences”, Information and Computation, 187:1 (2003), 49  
278. Hayato Takahashi, Kazuyuki Aihara, “Algorithmic analysis of irrational rotations in a single neuron model”, Journal of Complexity, 19:2 (2003), 132  
279. John M. Hitchcock, “Gales suffice for constructive dimension”, Information Processing Letters, 86:1 (2003), 9  
280. A. Romashchenko, 18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings., 2003, 221  
281. Stephen R. Tate, Lossless Compression Handbook, 2003, 35  
282. J. Suzuki, B. Ryabko, IEEE International Symposium on Information Theory, 2003. Proceedings., 2003, 113  
283. Yuri Kalnishkan, Volodya Vovk, Michael V. Vyugin, Lecture Notes in Computer Science, 2777, Learning Theory and Kernel Machines, 2003, 522  
284. Marcus Hutter, Lecture Notes in Computer Science, 2842, Algorithmic Learning Theory, 2003, 298  
285. Christa Sommerer, Laurent Mignonneau, Art and Complexity, 2003, 85  
286. Marcus Hutter, Lecture Notes in Computer Science, 2777, Learning Theory and Kernel Machines, 2003, 506  
287. Alexander Nabutovsky, Shmuel Weinberger, “The Fractal Nature of Riem/Diff I”, Geometriae Dedicata, 101:1 (2003), 1  
288. A. Yu. Khrennikov, “Interpretations of Probability and Their p-Adic Extensions”, Theory Probab Appl, 46:2 (2002), 256        
289. V.V. V'yugin, “Suboptimal Measures of Predictive Complexity for Absolute Loss Function”, Information and Computation, 175:2 (2002), 146  
290. Michael V Vyugin, Vladimir V V'yugin, “On Complexity of Easy Predictable Sequences”, Information and Computation, 178:1 (2002), 241  
291. Yuri Kalnishkan, “General linear relations between different types of predictive complexity”, Theoretical Computer Science, 271:1-2 (2002), 181  
292. Bruno Durand, Alexander Shen, Nikolai Vereshchagin, “Descriptive complexity of computable sequences”, Theoretical Computer Science, 271:1-2 (2002), 47  
293. Nikolai K. Vereshchagin, “Kolmogorov complexity conditional to large integers”, Theoretical Computer Science, 271:1-2 (2002), 59  
294. Bruno Durand, Sylvain Porrot, “Comparison between the complexity of a function and the complexity of its graph”, Theoretical Computer Science, 271:1-2 (2002), 37  
295. MARCUS HUTTER, “THE FASTEST AND SHORTEST ALGORITHM FOR ALL WELL-DEFINED PROBLEMS”, Int. J. Found. Comput. Sci, 13:03 (2002), 431  
296. Ludwig Staiger, “The Kolmogorov complexity of real numbers”, Theoretical Computer Science, 284:2 (2002), 455  
297. P. Gaspard, Lecture Notes in Physics, 597, Dynamics of Dissipation, 2002, 111  
298. Jürgen Schmidhuber, Lecture Notes in Computer Science, 2375, Computational Learning Theory, 2002, 216  
299. L.A. Levin, The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings., 2002, 761  
300. Michael V. Vyugin, Vladimir V. V'yugin, Lecture Notes in Computer Science, 2375, Computational Learning Theory, 2002, 90  
301. Marcus Hutter, “New Error Bounds for Solomonoff Prediction”, Journal of Computer and System Sciences, 62:4 (2001), 653  
302. V.V V'yugin, “Most Sequences Are Stochastic”, Information and Computation, 169:2 (2001), 252  
303. Marcus Hutter, Lecture Notes in Computer Science, 2167, Machine Learning: ECML 2001, 2001, 239  
304. Ilia Nouretdinov, Volodya Vovk, Michael Vyugin, Alex Gammerman, Lecture Notes in Computer Science, 2111, Computational Learning Theory, 2001, 337  
305. Victor Korotkich, Encyclopedia of Optimization, 2001, 1191  
306. Michael V. Vyugin, Vladimir V. V'yugin, Lecture Notes in Computer Science, 2225, Algorithmic Learning Theory, 2001, 190  
307. P.M.B. Vitanyi, Ming Li, “Minimum description length induction, Bayesianism, and Kolmogorov complexity”, IEEE Trans Inform Theory, 46:2 (2000), 446        
308. A. E. Romashchenko, “Pairs of Words with Nonmaterializable Mutual Information”, Problems Inform. Transmission, 36:1 (2000), 1–18      
309. C. Adami, N.J. Cerf, “Physical complexity of symbolic sequences”, Physica D: Nonlinear Phenomena, 137:1-2 (2000), 62  
310. Daniel Hammer, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin, “Inequalities for Shannon Entropy and Kolmogorov Complexity”, Journal of Computer and System Sciences, 60:2 (2000), 442  
311. Ludwig Staiger, Numbers, Information and Complexity, 2000, 403  
312. Jose Hernandez-Orallo, “Beyond the Turing Test”, Journal of Logic, Language and Information, 9:4 (2000), 447  
313. J Lathrop, “Recursive Computational Depth”, Information and Computation, 153:2 (1999), 139  
314. Yuri Kalnishkan, Proceedings of the twelfth annual conference on Computational learning theory, 1999, 226  
315. Bruno Durand, Alexander Shen, Nikolai Vereshagin, Lecture Notes in Computer Science, 1563, STACS 99, 1999, 153  
316. C.H. Bennett, P. Gacs, Ming Li, M.B. Vitanyi, W.H. Zurek, “Information distance”, IEEE Trans Inform Theory, 44:4 (1998), 1407        
317. An.A. Muchnik, “On common information”, Theoretical Computer Science, 207:2 (1998), 319  
318. V.V. V'yugin, “Ergodic theorems for individual random sequences”, Theoretical Computer Science, 207:2 (1998), 343  
319. V.V. V'yugin, “Non-stochastic infinite and finite sequences”, Theoretical Computer Science, 207:2 (1998), 363  
320. Andrei A. Muchnik, Alexei L. Semenov, Vladimir A. Uspensky, “Mathematical metaphysics of randomness”, Theoretical Computer Science, 207:2 (1998), 263  
321. Peter Hertling, Klaus Weihrauch, Lecture Notes in Computer Science, 1443, Automata, Languages and Programming, 1998, 796  
322. Bruno Durand, Sylvain Porrot, Lecture Notes in Computer Science, 1450, Mathematical Foundations of Computer Science 1998, 1998, 732  
323. V. Vovk, C. Watkins, Proceedings of the eleventh annual conference on Computational learning theory, 1998, 12  
324. D. Sow, A. Eleftheriadis, 1, Conference Record of Thirty-Second Asilomar Conference on Signals, Systems and Computers (Cat. No.98CH36284), 1998, 452  
325. En-hui Yang, Zhen Zhang, T. Berger, “Fixed-slope universal lossy data compression”, IEEE Trans Inform Theory, 43:5 (1997), 1465      
326. Jürgen Schmidhuber, “Discovering Neural Nets with Low Kolmogorov Complexity and High Generalization Capability”, Neural Networks, 10:5 (1997), 857    
327. Ming Li, Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 1997, 189  
328. Ming Li, Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 1997, 1  
329. D. Hammer, A.E. Romashchenko, A. Shen, N.K. Vereshchagin, Proceedings of Computational Complexity. Twelfth Annual IEEE Conference, 1997, 13  
330. Ming Li, Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 1997, 239  
331. Ming Li, Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 1997, 459  
332. Tao Jiang, Joel I. Seiferas, Paul M. B. Vitányi, “Two heads are better than two tapes”, J. ACM, 44:2 (1997), 237  
333. Ming Li, Paul Vitányi, An Introduction to Kolmogorov Complexity and Its Applications, 1997, 93  
334. Josef M. Breutzmann, Jack H. Lutz, Lecture Notes in Computer Science, 1200, STACS 97, 1997, 535  
335. Steven M. Kautz, Lecture Notes in Computer Science, 1269, Randomization and Approximation Techniques in Computer Science, 1997, 197  
336. Paul Vitányi, Ming Li, Lecture Notes in Computer Science, 1224, Machine Learning: ECML-97, 1997, 14  
337. J.C. Kieffer, En-hui Yang, “Sequential codes, lossless compression of individual sequences, and Kolmogorov complexity”, IEEE Trans Inform Theory, 42:1 (1996), 29        
338. A. Nabutovsky, “Geometry of the space of triangulations of a compact manifold”, Comm Math Phys, 181:2 (1996), 303          
339. V. A. Uspensky, A. Shen, “Relations between varieties of kolmogorov complexities”, Math Systems Theory, 29:3 (1996), 271          
340. Charles H. Bennett, “Universal computation and physical dynamics”, Physica D: Nonlinear Phenomena, 86:1-2 (1995), 268  
341. Ming Li, Paul Vitányi, Lecture Notes in Computer Science, 1000, Computer Science Today, 1995, 518  
342. I. G. Zhurbenko, O. S. Smirnova, “On an algorithm to generate weakly correlated random numbers”, J Math Sci, 75:2 (1995), 1576  
343. Evangelos Kranakis, Danny Krizanc, Flaminia L. Luccio, Lecture Notes in Computer Science, 969, Mathematical Foundations of Computer Science 1995, 1995, 392  
344. Charles H. Bennett, Computerkultur, 2, The Universal Turing Machine A Half-Century Survey, 1995, 207  
345. Moshe Koppel, Computerkultur, 2, The Universal Turing Machine A Half-Century Survey, 1995, 403  
346. Ray J. Solomonoff, Lecture Notes in Computer Science, 904, Computational Learning Theory, 1995, 1  
347. I. A. Vinogradova, A. G. El'kin, Yu. V. Prokhorov, B. A. Efimov, L. P. Kuptsov, N. Kh. Rozov, V. A. Oskolkov, L. D. Kudryavtsev, B. V. Khvedelidze, A. A. Zakharov, M. Sh. Tsalenko, E. D. Solomentsev, Yu. L. Ershov, I. V. Dolgachev, B. B. Venkov, A. N. Parshin, A. I. Kostrikin, A. B. Ivanov, A. P. Terekhin, V. F. Emelyanov, V. V. Sazonov, M. I. Voǐtsekhovskiǐ, I. I. Volkov, P. S. Aleksandrov, A. V. Prokhorov, A. M. Zubkov, V. N. Grishin, A. A. Danilevich, N. M. Nagornyǐ, E. G. D'yakonov, Kh. D. Ikramov, N. S. Bakhvalov, A. V. Arkhangel'skiǐ, V. V. Rumyantsev, A. V. Zarelua, A. A. Mal'tsev, O. A. Ivanova, V. P. Fedotov, I. P. Kubilyus, B. M. Bredikhin, P. L. Dobrushin, V. V. Prelov, A. V. Mikhalev, V. A. Andrunakievich, V. V. Fedorchuk, V. P. Platonov, A. P. Favorskiǐ, D. V. Anosov, V. I. Danilov, E. L. Tonkov, A. L. Onishchik, T. S. Pigolkina, T. S. Pogolkina, L. A. Skornyakov, V. I. Sobolev, I. Kh. Sabitov, V. I. Lebedev, A. V. Lykov, A., Encyclopaedia of Mathematics, 1995, 1  
348. B. Schapiro, “An approach to the physics of complexity”, Chaos, Solitons & Fractals, 4:1 (1994), 115  
349. David W. Juedes, James I. Lathrop, Jack H. Lutz, “Computational depth and reducibility”, Theoretical Computer Science, 132:1-2 (1994), 37  
350. V. G. Vovk, V. V. V'Yugin, “Prequential Level of Impossibility with Some Applications”, Journal of the Royal Statistical Society Series B: Statistical Methodology, 56:1 (1994), 115  
351. P. Gacs, Proceedings Workshop on Physics and Computation. PhysComp '94, 1994, 209  
352. Rafail Krichevsky, Universal Compression and Retrieval, 1994, 27  
353. A. Nabutovsky, R. Ben-Av, “Noncomputability arising in dynamical triangulation model of four-dimensional Quantum Gravity”, Comm Math Phys, 157:1 (1993), 93          
354. Peter Bro Miltersen, “The Complexity of Malign Measures”, SIAM J Comput, 22:1 (1993), 147          
355. Homer S. White, “Algorithmic complexity of points in dynamical systems”, Ergod Th Dynam Sys, 13:4 (1993)      
356. Pierre Gaspard, Xiao-Jing Wang, “Noise, chaos, and (ε, τ)-entropy per unit time”, Physics Reports, 235:6 (1993), 291  
357. Manuel Martinez-Morales, B.S. Duran, “A test for randomness based on a complexity measure”, Communications in Statistics - Theory and Methods, 22:3 (1993), 879  
358. Luc Longpré, Sarah Mocas, “Symmetry of information and one-way functions”, Information Processing Letters, 46:2 (1993), 95  
359. Randomness and Undecidability in Physics, 1993, 243  
360. David W. Juedes, James I. Lathrop, Jack H. Lutz, Lecture Notes in Computer Science, 700, Automata, Languages and Programming, 1993, 277  
361. László Gerencsér, Jorma Rissanen, The IMA Volumes in Mathematics and its Applications, 46, New Directions in Time Series Analysis, 1993, 93  
362. A. Kh. Shen, Mathematics and Its Applications, 27, Selected Works of A. N. Kolmogorov, 1993, 226  
363. Jean-Paul Delahaye, Philosophy of Probability, 1993, 145  
364. A. N. Shiryayev, Mathematics and Its Applications, 27, Selected Works of A. N. Kolmogorov, 1993, 208  
365. Ming Li, Paul M.B. Vitányi, “Inductive reasoning and kolmogorov complexity”, Journal of Computer and System Sciences, 44:2 (1992), 343  
366. Ming Li, Paul M.B. Vitányi, “Average case complexity under the universal distribution equals worst-case complexity”, Information Processing Letters, 42:3 (1992), 145  
367. Vladimir A. Uspensky, Kolmogorov Complexity and Computational Complexity, 1992, 85  
368. C.H. Bennett, Workshop on Physics and Computation, 1992, 75  
369. Ming Li, P. Vitanyi, Workshop on Physics and Computation, 1992, 42  
370. Luc Longpré, Osamu Watanabe, Lecture Notes in Computer Science, 650, Algorithms and Computation, 1992, 410  
371. P R Baldwin, J Phys A Math Gen, 24:16 (1991), L941          
372. Moshe Koppel, Henri Atlan, “An almost machine-independent theory of program-length complexity, sophistication, and induction”, Information Sciences, 56:1-3 (1991), 23  
373. Yuri Gurevich, “Average case completeness”, Journal of Computer and System Sciences, 42:3 (1991), 346  
374. P.E. Rapp, M.A. Jiménez-Montano, R.J. Langs, L. Thomson, A.I. Mees, “Toward a quantitative characterization of patient-therapist communication”, Mathematical Biosciences, 105:2 (1991), 207  
375. Y Yomdin, “Complexity of functions: Some questions, conjectures, and results”, Journal of Complexity, 7:1 (1991), 70  
376. Luigi Burigana, “Organization by rules in finite sequences”, Journal of Mathematical Psychology, 35:3 (1991), 345  
377. Dung T. Huyn, “Effective entropies and data compression”, Information and Computation, 90:1 (1991), 67  
378. Ming Li, Paul Vitányi, SIAM J. Comput, 20:5 (1991), 911  
379. Luc Longpré, Sarah Mocas, Lecture Notes in Computer Science, 557, ISA'91 Algorithms, 1991, 308  
380. L. Gerencser, [1991] Proceedings. Data Compression Conference, 1991, 228  
381. P.B. Miltersen, [1991] Proceedings of the Sixth Annual Structure in Complexity Theory Conference, 1991, 164  
382. Rūsiņš Freivalds, Jānis Bārzdiņš, Kārlis Podnieks, Lecture Notes in Computer Science, 502, Baltic Computer Science, 1991, 111  
383. Karl Svozil, “Comment on ‘`Comment on `Quantum cosmology and the initial state of the universe’ "”, Phys Rev D, 41:4 (1990), 1353    
384. V. A. Uspenskii, A. L. Semenov, A. Kh. Shen', “Can an individual sequence of zeros and ones be random?”, Russian Math. Surveys, 45:1 (1990), 121–189            
385. Karl Svozil, “Constructive chaos by cellular automata and possible sources of an arrow of time”, Physica D: Nonlinear Phenomena, 45:1-3 (1990), 420  
386. Ramamohan Paturi, Joel I. Seiferas, Janos Simon, Richard E. Newman-Wolfe, “Milking the Aanderaa argument”, Information and Computation, 88:1 (1990), 88  
387. Ming Li, Paul M. B. Vitányi, Complexity Theory Retrospective, 1990, 147  
388. Ming LI, Paul M.B. VITÁNYI, Algorithms and Complexity, 1990, 187  
389. R. Impagliazzo, L.A, Levin, Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, 1990, 812  
390. Ludwig Staiger, Lecture Notes in Computer Science, 380, Fundamentals of Computation Theory, 1989, 434  
391. M. Li, P.M.B. Vitanyi, 30th Annual Symposium on Foundations of Computer Science, 1989, 34  
392. M. Li, P.M.B. Vitanyi, [1989] Proceedings. Structure in Complexity Theory Fourth Annual Conference, 1989, 165  
393. Kristian Lindgren, “Microscopic and macroscopic entropy”, Phys Rev A, 38:9 (1988), 4794    
394. P. Vitani, M. Li, “Kolmogorovskaya slozhnost: dvadtsat let spustya”, UMN, 43:6(264) (1988), 129–166      
395. J. Higgins, “Embedding recursive functions in universal algorithms”, International Journal of Computer Mathematics, 24:3-4 (1988), 273  
396. M. Hazewinkel, Encyclopaedia of Mathematics, 1988, 1  
397. H Atlan, “Self creation of meaning”, Phys Scr, 36:3 (1987), 563      
398. A. N. Kolmogorov, V. A. Uspenskii, “Algorithms and Randomness”, Theory Probab Appl, 32:3 (1987), 389          
399. Y. Oono, C. Yeung, “A cell dynamical system model of chemical turbulence”, J Stat Phys, 48:3-4 (1987), 593  
400. Ker-I Ko, “On the notion of infinite pseudorandom sequences”, Theoretical Computer Science, 48 (1986), 9  
401. Dung T. Huynh, Lecture Notes in Computer Science, 223, Structure in Complexity Theory, 1986, 184  
402. Thomas M. Cover, The Impact of Processing Techniques on Communications, 1985, 23  
403. M. A. Jiménez-Montaño, “On the syntactic structure of protein sequences and the concept of grammar complexity”, Bull Math Biol, 46:4 (1984), 641        
404. E. A. Asarin, “On convergence of uniform approximations of continuous functions”, Russian Math. Surveys, 39:3 (1984), 179–193            
405. Edward P. Stabler, “Berwick and Weinberg on linguistics and computational psychology”, Cognition, 17:2 (1984), 155  
406. Leonid A. Levin, “Randomness conservation inequalities; information and independence in mathematical theories”, Information and Control, 61:1 (1984), 15  
407. B.A. Trakhtenbrot, “A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms”, IEEE Annals Hist. Comput., 6:4 (1984), 384  
408. O. Goldreich, S. Goldwasser, S. Micali, 25th Annual Symposium onFoundations of Computer Science, 1984., 1984, 464  
409. A. Muir, M. W. Warner, “The dynamics of symmetric nets”, Bull Math Biol, 45:5 (1983), 781        
410. A. N. Kolmogorov, “Combinatorial foundations of information theory and the calculus of probabilities”, Russian Math. Surveys, 38:4 (1983), 29–40            
411. M. Milgram, H. Atlan, “Probabilistic automata as a model for epigenesis of cellular networks”, Journal of Theoretical Biology, 103:4 (1983), 523  
412. Péter Gács, “On the relation between descriptional complexity and algorithmic probability”, Theoretical Computer Science, 22:1-2 (1983), 71  
413. Stuart A. Kurtz, “On the random oracle hypothesis”, Information and Control, 57:1 (1983), 40  
414. A. N. Kolmogorov, Lecture Notes in Mathematics, 1021, Probability Theory and Mathematical Statistics, 1983, 1  
415. J. P. Crutchfield, N. H. Packard, “Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise”, Int J Theor Phys, 21:6-7 (1982), 433        
416. Charles H. Bennett, “The thermodynamics of computation—a review”, Int J Theor Phys, 21:12 (1982), 905    
417. Andrew C. Yao, 23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), 1982, 80  
418. Peter Gács, “Exact Expressions for Some Randomness Tests”, Z Math Logik Grundlagen Math, 26:25-27 (1980), 385        
419. Gary L. Peterson, 21st Annual Symposium on Foundations of Computer Science (sfcs 1980), 1980, 86  
420. J.M. Maciejowski, “Model discrimination using an algorithmic information criterion”, Automatica, 15:5 (1979), 579  
421. Péter Gács, Lecture Notes in Computer Science, 67, Theoretical Computer Science 4th GI Conference, 1979, 124  
422. A. A. Brudno, “The complexity of the trajectories of a dynamical system”, Russian Math. Surveys, 33:1 (1978), 197–198        
423. R. Solomonoff, “Complexity-based induction systems: Comparisons and convergence theorems”, IEEE Trans. Inform. Theory, 24:4 (1978), 422  
424. S. Leung-Yan-Cheong, T. Cover, “Some equivalences between Shannon entropy and Kolmogorov complexity”, IEEE Trans. Inform. Theory, 24:3 (1978), 331  
425. Robert Daley, “On the inference of optimal descriptions”, Theoretical Computer Science, 4:3 (1977), 301  
426. Jan M. Maciejowski, “The Assessment of Rival Models of the Same Finite Set of Observations”, IFAC Proceedings Volumes, 10:7 (1977), 227  
427. C. P. Schnorr, Basic Problems in Methodology and Linguistics, 1977, 193  
428. R.P.. Daley, “Noncomplex sequences: characterizations and examples”, J. symb. log, 41:03 (1976), 626  
429. Robert P. Daley, “Noncomplex sequences: characterizations and examples”, J. symb. log., 41:3 (1976), 626  
430. R. V. Freivald, Lecture Notes in Computer Science, 28, Mathematical Foundations of Computer Science, 1975, 77  
431. Gregory J. Chaitin, “Information-Theoretic Limitations of Formal Systems”, J. ACM, 21:3 (1974), 403