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.
Document type :
Complete list of metadatas

Contributor : Publications Loria <>
Submitted on : Monday, September 25, 2006 - 5:03:29 PM
Last modification on : Friday, January 4, 2019 - 5:33:34 PM


  • 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⟩



Record views