97-74: Upper semi-lattice of binary strings with the relation ``x is simple conditional to y''

DIMACS TR: 97-74

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

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1997/97-74.ps.gz

DIMACS Home Page