paperbot · PL 论文追踪

全部论文 待读 收藏

P2 The Ho-Zhao Problem

Ho–Zhao 问题
LMCS vol.Volume 14, Issue 12018匹配度 1/10 · 该论文研究dcpo范畴与Γ-faithful性质,属于纯序理论/域理论的形式语义工作,与用户关注的PL→AI静态分析、Agentic程序、浮点程序分析、贝叶斯程序分析及LLM交叉方向基本无关。引用 0 inbox
Weng Kin Ho, Jean Goubault-Larrecq, Achim Jung, Xiaoyong Xi
crossref: 2026-09-10

AI 速览

一句话:否定 Ho–Zhao 问题:证明 dcpo 范畴并非 Γ-faithful,并引入涵盖已知情形的 Γ-faithful dcpo 子范畴。

论文研究 Scott 闭集格 Γ(P) 能否决定偏序集 P 的范畴论问题。给定偏序集 P,其所有 Scott 闭集按包含序构成完备格 Γ(P);若子范畴 C 中 Γ(P)≅Γ(Q) 蕴含 P≅Q,则称 C 为 Γ-faithful。已知连续 dcpo 与有界完备 dcpo 具有该性质,而 Pos_d 不具有;Ho 与 Zhao (2009) 询问 dcpo 范畴 DCPO 是否 Γ-faithful。本文给出否定回答:通过构造反例证明 DCPO 不是 Γ-faithful。为构造反例,作者引入一个新的 dcpo 子范畴,证明其为 Γ-faithful,且涵盖当时所有已知的 Γ-faithful 子范畴;反例构造关键依赖于 Johnstone 那个在 Scott 拓扑下非 sober 的 dcpo。

问题
问题:判定 dcpo 范畴 DCPO 是否 Γ-faithful,即对任意 dcpo P,Q,Γ(P)≅Γ(Q) 是否必有 P≅Q。
方法
方法:引入一个新的 dcpo 子范畴并证明其 Γ-faithful,该子范畴包含所有已知 Γ-faithful 子范畴;在此基础上构造依赖 Johnstone 非 sober dcpo 的反例。
评估
评估:以显式反例否定 Ho–Zhao 问题,并给出更一般的 Γ-faithful 子范畴结果。
原文摘要(Abstract)

Given a poset $P$, the set, $\Gamma(P)$, of all Scott closed sets ordered by inclusion forms a complete lattice. A subcategory $\mathbf{C}$ of $\mathbf{Pos}_d$ (the category of posets and Scott-continuous maps) is said to be $\Gamma$-faithful if for any posets $P$ and $Q$ in $\mathbf{C}$, $\Gamma(P) \cong \Gamma(Q)$ implies $P \cong Q$. It is known that the category of all continuous dcpos and the category of bounded complete dcpos are $\Gamma$-faithful, while $\mathbf{Pos}_d$ is not. Ho & Zhao (2009) asked whether the category $\mathbf{DCPO}$ of dcpos is $\Gamma$-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 $\Gamma$-faithful. This subcategory subsumes all currently known $\Gamma$-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.Comment: 19 pages, 4 figures

链接与引用

DOI 原文 · PDF(开放获取) ·

BibTeX
@article{paperbot434,
  title = {The Ho-Zhao Problem},
  author = {Weng Kin Ho and Jean Goubault-Larrecq and Achim Jung and Xiaoyong Xi},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 14, Issue 1},
  year = {2018},
  doi = {10.23638/lmcs-14(1:7)2018}
}