Upper Semi-Lattice of Binary Strings with the Relation ``$x$ is simple conditional to $y$''
Andrei Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshagin

Abstract:
Upper semi­lattice of binary strings with the relation 
 ``x is simple conditional to y''
Andrei Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshagin

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 G'acs and K¨orner result).