## 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