Kolmogorov complexity and non-determinism

Serge Grigorieff 1 Jean-Yves Marion 2
2 CALLIGRAMME - Linear logic, proof networks and categorial grammars
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : We are concerned with Kolmogorov complexity of strings produced by non-deterministic algorithms. For this, we consider binary recursively enumerable relations, named description modes. We give conditions on the class of description modes to provide a Kolmogorov entropy. Within this framework, we prove that there is a proper hierarchy of such non-deterministic modes. Then, we give a sharp estimation on the amount of information to turn a deterministic mode into a non-deterministic one, and inversely. Lastly, we show that deterministic modes are less efficient than non-deterministic modes from some rank.
Type de document :
[Intern report] 98-R-274 || grigorieff98a, 1998, 11 p
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : lundi 25 septembre 2006 - 17:03:29
Dernière modification le : jeudi 15 novembre 2018 - 20:27:40


  • HAL Id : inria-00098564, version 1



Serge Grigorieff, Jean-Yves Marion. Kolmogorov complexity and non-determinism. [Intern report] 98-R-274 || grigorieff98a, 1998, 11 p. 〈inria-00098564〉



Consultations de la notice