### Abstract

Original language | English |
---|---|

Pages (from-to) | 69-95 |

Number of pages | 27 |

Journal | Theoretical Computer Science |

Volume | 271 |

Issue number | 1-2 |

DOIs | |

Publication status | Published - 28 Jan 2002 |

### Fingerprint

### Keywords

- Kolmogorov complexity
- common information
- conditional complexity

### Cite this

*Theoretical Computer Science*,

*271*(1-2), 69-95. https://doi.org/10.1016/S0304-3975(01)00032-9

}

*Theoretical Computer Science*, vol. 271, no. 1-2, pp. 69-95. https://doi.org/10.1016/S0304-3975(01)00032-9

**Upper semi-lattice of binary strings with the relation "x is simple conditional to y".** / Chernov, Alexey; Muchnik, Andrej; Romashchenko, Andrei; Shen, Alexander; Vereshchagin, Nikolai.

Research output: Contribution to journal › Article

TY - JOUR

T1 - Upper semi-lattice of binary strings with the relation "x is simple conditional to y"

AU - Chernov, Alexey

AU - Muchnik, Andrej

AU - Romashchenko, Andrei

AU - Shen, Alexander

AU - Vereshchagin, Nikolai

PY - 2002/1/28

Y1 - 2002/1/28

N2 - In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x `<=` y means that K(x|y)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner(Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) Wede4ne a notion of “complexity profile” of the pair of elements of R and give (exact) upper andlower bounds for it in a particular case.

AB - In this paper we construct a structure R that is a “finite version” of the semi-lattice of Turing degrees. Its elements are strings (technically, sequences of strings) and x `<=` y means that K(x|y)=(conditional Kolmogorov complexity of x relative to y) is small. We construct two elements in R that do not have greatest lower bound. We give a series of examples that show how natural algebraic constructions give two elements that have lower bound 0 (minimal element) but significant mutual information. (A first example of that kind was constructed by Gács–Körner(Problems Control Inform. Theory 2 (1973) 149) using a completely different technique.) Wede4ne a notion of “complexity profile” of the pair of elements of R and give (exact) upper andlower bounds for it in a particular case.

KW - Kolmogorov complexity

KW - common information

KW - conditional complexity

U2 - 10.1016/S0304-3975(01)00032-9

DO - 10.1016/S0304-3975(01)00032-9

M3 - Article

VL - 271

SP - 69

EP - 95

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1-2

ER -