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 semilattice 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 preorder. 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).