Upper semi-lattice of binary strings with the relation
``x is simple conditional to y''
Authors: Andrei Muchnik, Andrei Romashchenko, Alexander Shen and
Nikolai Vereshagin
ABSTRACT
We study the properties of the set of binary strings with the relation
``the Kolmogorov complexity of x conditional to y is small''.
We prove that there are pairs of strings which have no greatest
common lower bound with respect to
this pre-order. We present several examples when the greatest common lower
bound exists but its complexity is much less than mutual information
(extending the Gacs and Koerner result).
DIMACS Home Page