paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Constructive Domains with Classical Witnesses

带经典见证的构造性Domain
LMCS vol.Volume 17, Issue 12021匹配度 3/10 · 该论文属于构造性Domain理论与程序抽取/形式语义,与用户核心关注的静态分析、Agentic程序、LLM辅助形式化验证、浮点或贝叶斯程序分析均无直接交集;仅实数表示定理与可计算实数/浮点形式化有非常间接的联系。引用 5 inbox
Dirk Pattinson, Mina Mohammadian
crossref: 2026-09-10

AI 速览

一句话:提出从程序抽取视角出发、以经典正确性断言实现的构造性连续Domain理论,并给出函数空间与实数表示定理。

本文从程序抽取的视角建立连续Domain的构造性理论。其目标是使抽取出的程序表示可证明正确的计算,却不携带正确性见证;为此,作者以经典逻辑形式陈述正确性断言。技术上,论文从predomain基出发构造completion,并围绕Scott拓扑研究连续性,给出函数空间的构造。作者详细讨论主要动机例子,并将理论实例化到实数:将实数视为有理区间predomain之completion的全元素,进而证明一个表示定理,精确刻画可表示的连续函数类。

问题
如何在程序抽取中让程序代表可证明正确的计算,同时避免在程序中携带正确性见证。
方法
从predomain基构造completion,在Scott拓扑下研究连续性并构造函数空间,并以经典方式表述正确性断言。
评估
通过详细动机案例和实数实例(有理区间predomain completion的全元素)证明表示定理,刻画可表示的连续函数类。
原文摘要(Abstract)

We develop a constructive theory of continuous domains from the perspective of program extraction. Our goal that programs represent (provably correct) computation without witnesses of correctness is achieved by formulating correctness assertions classically. Technically, we start from a predomain base and construct a completion. We then investigate continuity with respect to the Scott topology, and present a construction of the function space. We then discuss our main motivating example in detail, and instantiate our theory to real numbers that we conceptualise as the total elements of the completion of the predomain of rational intervals, and prove a representation theorem that precisely delineates the class of representable continuous functions.

链接与引用

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

BibTeX
@article{paperbot1332,
  title = {Constructive Domains with Classical Witnesses},
  author = {Dirk Pattinson and Mina Mohammadian},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 1},
  year = {2021},
  doi = {10.23638/lmcs-17(1:19)2021}
}