paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Almost Fair Simulations

几乎公平模拟
ICFP 9(ICFP)2025匹配度 2/10 · 论文属于纯形式化验证/定理证明方向,研究公平模拟与Büchi公平迹包含,不涉及用户核心关注的静态分析、Agentic程序、LLM辅助形式化验证、浮点程序分析或贝叶斯程序分析。仅在“形式化验证”这一宽泛领域上与用户画像有微弱关联。引用 1 inbox
Arthur Correnson, Iona Kuhn, Bernd Finkbeiner
crossref: 2026-09-10

AI 速览

一句话:提出一族几乎公平模拟关系及演绎系统,用于证明带Büchi公平条件的迁移系统的公平迹包含。

标准模拟无法证明活性性质;公平模拟虽可处理公平性假设与要求,但定义常涉及归纳与余归纳的复杂嵌套,难以用于交互式验证。本文针对带 Büchi 公平条件的迁移系统,从已有公平模拟技术出发,逐步构造一族 almost fair simulation 关系,控制不动点交替,并为每种关系给出直观推理规则,形成证明公平迹包含的演绎系统。作者在 Rocq 证明助手中机器化这些关系及演绎系统,证明其可靠性,并通过若干示例展示其可用性。

问题
标准模拟不能证明活性性质,而公平模拟定义中归纳与余归纳嵌套复杂,尤其难以用于交互式验证。
方法
针对带 Büchi 公平条件的迁移系统,逐步构造一族 almost fair simulation 关系,控制不动点交替,并配套直观推理规则与演绎系统。
评估
在 Rocq 中机器化关系与演绎系统,证明其可靠性,并通过示例展示其使用。
原文摘要(Abstract)

It is well known that liveness properties cannot be proven using standard simulation arguments. This issue has been mitigated by extending standard notions of simulation for transition systems to fairness-preserving simulations for systems equipped with an additional fairness condition modeling liveness assumptions and/or liveness requirements. In the context of automated verification of finite-state systems, proofs by simulation are an appealing method as there exist efficient algorithms to find a simulation between two systems. However, applications of fair simulation to interactive verification have been much less studied. Perhaps one reason is that the definitions of fair simulation relations typically involve non-trivial nestings of inductive and coinductive relations, making them particularly difficult to use and to reason about. In this paper, we argue that in many cases, stronger notions of fair simulation involving more controlled alternations of fixed points are sufficient. Starting from known fair simulation techniques, we progressively build up a family of almost fair simulation relations for transition systems equipped with a Büchi fairness condition. The simulation relations we present can all be equipped with intuitive reasoning rules, leading to elegant deductive systems to prove fair trace inclusion. We mechanized our simulation relations and their associated deductive systems in the Rocq proof assistant, proved their soundness, and we demonstrate their use through a selection of examples.

链接与引用

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

BibTeX
@article{paperbot3055,
  title = {Almost Fair Simulations},
  author = {Arthur Correnson and Iona Kuhn and Bernd Finkbeiner},
  journal = {Proceedings of the ACM on Programming Languages},
  volume = {9},
  number = {ICFP},
  year = {2025},
  doi = {10.1145/3747512}
}