提出可验证的逻辑规约框架,确保求解结果与原始问题一致
Towards a Certifying Grounder
- 设计新型规范形式GNF,实现紧凑且依赖域信息的规约
- 生成可验证的证明文件,确保规约结果等价于原问题
- 适合需要可信求解的工业级声明式编程场景
规约是将高层理论转化为等价无量词公式的必要步骤,但至今未纳入证明日志体系。非可验证规约导致用户无法确认求解结果是否真实对应原始问题,形成信任缺口。本文提出针对有限域上一阶逻辑模型扩展(FOX)的新型可验证规约框架CertiFOX,包含:(1) 规约推导的证明格式;(2) 基于新规范形式GNF的可验证规约器GroundFOX;(3) 独立的证明检查器CheckFOX。该方法确保规约输出与输入规格等价,为声明式语言构建端到端可信求解流水线奠定基础。实验表明,CertiFOX可行:GroundFOX性能与现有规约器相当,CheckFOX验证开销仅为规约时间的小常数倍。
原文摘要 · Abstract (English)
Grounding, the translation of high-level theories into equivalent quantifier-free formulas, is a crucial step in declarative solving, yet it has so far escaped the proof-logging revolution. When this grounding step is not certifying, there is no way of knowing that the obtained solutions actually correspond to the original problem specification, resulting in a trust gap. In this paper, we close the trust gap between the user's high-level specification and the solver's low-level input by introducing a novel certifying grounding framework for first-order logic model expansion (FOX) over finite domains. We present CertiFOX, a framework consisting of: (1) a proof format for grounding derivations, (2) GroundFOX, a certifying grounder operating on theories in Grounding Normal Form (GNF)--a new normal form designed for compact, domain-aware grounding--and (3) CheckFOX, an independent proof checker. Our approach guarantees that the grounder's output is equivalent to the input specification, setting the stage for trustworthy end-to-end certified solving pipelines for declarative languages. Experimental evaluation confirms that CertiFOX is a feasible approach. The GroundFOX grounder is broadly comparable with other grounders, and proof checking with CheckFOX adds overhead within a small constant factor of grounding time.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。