Weng Kin Ho ; Jean Goubault-Larrecq ; Achim Jung ; Xiaoyong Xi - The Ho-Zhao Problem

lmcs:1529 - Logical Methods in Computer Science, January 17, 2018, Volume 14, Issue 1 - https://doi.org/10.23638/LMCS-14(1:7)2018
The Ho-Zhao ProblemArticle

Authors: Weng Kin Ho ; Jean Goubault-Larrecq ; Achim Jung ; Xiaoyong Xi

    Given a poset P, the set, Γ(P), of all Scott closed sets ordered by inclusion forms a complete lattice. A subcategory C of Posd (the category of posets and Scott-continuous maps) is said to be Γ-faithful if for any posets P and Q in C, Γ(P)Γ(Q) implies PQ. It is known that the category of all continuous dcpos and the category of bounded complete dcpos are Γ-faithful, while Posd is not. Ho & Zhao (2009) asked whether the category DCPO of dcpos is Γ-faithful. In this paper, we answer this question in the negative by exhibiting a counterexample. To achieve this, we introduce a new subcategory of dcpos which is Γ-faithful. This subcategory subsumes all currently known Γ-faithful subcategories. With this new concept in mind, we construct the desired counterexample which relies heavily on Johnstone's famous dcpo which is not sober in its Scott topology.


    Volume: Volume 14, Issue 1
    Published on: January 17, 2018
    Accepted on: December 21, 2017
    Submitted on: July 13, 2016
    Keywords: Computer Science - Logic in Computer Science,06B35
    Funding:
      Source : OpenAIRE Graph
    • Computing with Infinite Data; Funder: European Commission; Code: 731143

    Consultation statistics

    This page has been seen 2865 times.
    This article's PDF has been downloaded 725 times.