paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A cartesian-closed category for higher-order model checking

用于高阶模型检测的笛卡尔闭范畴
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 2/10 · 该论文属于形式语义、逻辑与自动机方向的高阶模型检测理论研究,与用户关注的静态分析/形式化验证有间接理论基础关联;但它不涉及 LLM/Agent 与 PL 的交叉、浮点程序分析或贝叶斯程序分析,也未体现工业落地或问题驱动的 benchmark 研究。引用 12 inbox
Martin Hofmann, Jeremy Ledent
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:为高阶模型检测构造笛卡尔闭范畴,并借助Büchi自动机的有限抽象格实现忠实抽象与不动点计算。

本文围绕标题所示的高阶模型检测笛卡尔闭范畴展开,研究其范畴论与抽象语义基础。摘要回顾了先前从给定Büchi自动机构造抽象格的方法:该抽象格是有限的,并与给定字母表上有限字和无限字语言构成的格之间存在Galois插入。该抽象对于自动机的接受性保持忠实,即可通过抽象层信息判断原自动机是否接受。进一步,最小不动点和ω迭代可以在抽象格层面计算,而最大不动点一般不具此性质。这些结果为在高阶模型检测中利用有限抽象进行不动点推理提供了语义与代数基础。

问题
如何为高阶模型检测建立合适的范畴论与语义基础。
方法
利用从Büchi自动机构造的有限抽象格,建立其与有限/无限字语言格之间的Galois插入,并在笛卡尔闭范畴框架下组织抽象与不动点计算。
评估
以理论构造和性质证明为主,关键评估点是抽象对自动机接受性的忠实性以及最小不动点、ω迭代的可计算性;摘要未提及实验评估。
原文摘要(Abstract)

In previous work we have described the construction of an abstract lattice from a given Büchi automaton. The abstract lattice is finite and has the following key properties. (i) There is a Galois insertion between it and the lattice of languages of finite and infinite words over a given alphabet. (ii) The abstraction is faithful with respect to acceptance by the automaton. (iii) Least fixpoints and ω-iterations (but not in general greatest fixpoints) can be computed on the level of the abstract lattice.

链接与引用

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

BibTeX
@inproceedings{HofmannL17,
  title = {A cartesian-closed category for higher-order model checking},
  author = {Martin Hofmann and Jeremy Ledent},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005120}
}