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 journalArticle

    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.
    LanguageEnglish
    Pages69-95
    Number of pages27
    JournalTheoretical Computer Science
    Volume271
    Issue number1-2
    DOIs
    StatePublished - 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, 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". 271(1-2), 69-95. DOI: 10.1016/S0304-3975(01)00032-9
    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. DOI: 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 journalArticle

    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 -

    Chernov A, Muchnik A, Romashchenko A, Shen A, Vereshchagin N. Upper semi-lattice of binary strings with the relation "x is simple conditional to y". 2002 Jan 28;271(1-2):69-95. Available from, DOI: 10.1016/S0304-3975(01)00032-9