To compare various standard definitions of Kolmogorov complexities, Uspensky and Shen introduce the concept of description modes
In essence, a description mode is a binary recursively enumerable relation. So when a description mode turns out to be the graph of a function, it denotes a deterministic computation.
We shall study various kinds of description modes in which a program may output more than one string.
From this, we attempt to investigate the information content of a string when we deal with non-deterministic algorithms.
A paper is available from http://www.loria.fr/~marionjy/research.html