Theoretical Computer Science, Volume 271

Volume 271, Number 1-2, January 2002

• Bruno Durand:
  Kolmogorov Complexity - Foreword. 1
  
• Cristian Calude:
  A characterization of c.e. random reals. 3-14
  
• Andrei A. Muchnik, Semen Ye. Positselsky:
  Kolmogorov entropy in the context of computability theory. 15-35
  
• Bruno Durand, Sylvain Porrot:
  Comparison between the complexity of a function and the complexity of its graph. 37-46
  
• Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin:
  Descriptive complexity of computable sequences. 47-58
  
• Nikolai K. Vereshchagin:
  Kolmogorov complexity conditional to large integers. 59-67
  
• Alexey V. Chernov, Andrei A. Muchnik, Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
  Upper semi-lattice of binary strings with the relation "x is simple conditional to y". 69-95
  
• Andrei A. Muchnik:
  Conditional complexity and codes. 97-109
  
• Andrei E. Romashchenko, Alexander Shen, Nikolai K. Vereshchagin:
  Combinatorial interpretation of Kolmogorov complexity. 111-123
  
• Alexander Shen, Nikolai K. Vereshchagin:
  Logical operations and Kolmogorov complexity. 125-129
  
• Nikolai K. Vereshchagin, Michael V. Vyugin:
  Independent minimum length programs to translate between given strings. 131-143
  
• Michael V. Vyugin:
  Information distance and conditional complexities. 145-150
  
• Serge Grigorieff, Jean-Yves Marion:
  Kolmogorov complexity and non-determinism. 151-180
  
• Yuri Kalnishkan:
  General linear relations between different types of predictive complexity. 181-200