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

Alexey Chernov, Andrej Muchnik, Andrei Romashchenko, Alexander Shen, Nikolai Vereshchagin

Research output: Contribution to journalArticleResearchpeer-review

Abstract

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.
Original languageEnglish
Pages (from-to)69-95
Number of pages27
JournalTheoretical Computer Science
Volume271
Issue number1-2
DOIs
Publication statusPublished - 28 Jan 2002

Fingerprint

Semilattice
Strings
Binary
Lower bound
Turing Degrees
Kolmogorov Complexity
K-means
Mutual Information
Control Problem
Upper bound
Series
Profile

Keywords

  • Kolmogorov complexity
  • common information
  • conditional complexity

Cite this

Chernov, Alexey ; Muchnik, Andrej ; Romashchenko, Andrei ; Shen, Alexander ; Vereshchagin, Nikolai. / Upper semi-lattice of binary strings with the relation "x is simple conditional to y". 2002 ; Vol. 271, No. 1-2. pp. 69-95.
@article{fa37f92454b94e448daf855e09ff11e3,
title = "Upper semi-lattice of binary strings with the relation {"}x is simple conditional to y{"}",
abstract = "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{\'a}cs–K{\"o}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.",
keywords = "Kolmogorov complexity, common information, conditional complexity",
author = "Alexey Chernov and Andrej Muchnik and Andrei Romashchenko and Alexander Shen and Nikolai Vereshchagin",
year = "2002",
month = "1",
day = "28",
doi = "10.1016/S0304-3975(01)00032-9",
language = "English",
volume = "271",
pages = "69--95",
number = "1-2",

}

Chernov, A, Muchnik, A, Romashchenko, A, Shen, A & Vereshchagin, N 2002, 'Upper semi-lattice of binary strings with the relation "x is simple conditional to y"' 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.

Vol. 271, No. 1-2, 28.01.2002, p. 69-95.

Research output: Contribution to journalArticleResearchpeer-review

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

IS - 1-2

ER -