paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Zigzag normalisation for associative n-categories

结合 n-范畴的 Zigzag 规范化
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 该论文属于高阶范畴论、项规范化与证明助手的形式语义工作,与用户关注的静态分析、LLM/Agent、浮点程序分析、贝叶斯程序分析均无直接关联。仅在“形式化验证/证明工程”这一宽泛方向上与 AI→PL 的交叉兴趣有很弱的联系。引用 6 inbox
Lukas Heidemann, David Reutter, Jamie Vicary
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出结合 n-范畴项规范化的 zigzag 构造算法,证明其正确性,并用于证明助手 homotopy.io。

Associative n-范畴为高阶范畴论提供了一种严格结合且含单位的表述,有望作为证明助手的基础,从而形式化复杂的高维代数现象。然而,该理论依赖隐式的项规范化过程来判定正确的复合,此前没有可递归计算的方法。本文基于范畴的 zigzag 构造提出新的项规范化方法,显著简化理论,并给出递归规范化算法,证明其正确性。作者利用范畴提升性质高效证明结果。该算法已成为证明助手 homotopy.io 的核心组件,文中还给出多个实例说明其工作方式。

问题
结合 n-范畴理论依赖隐式项规范化来识别正确复合,但缺少可递归计算的方法,难以支撑证明助手。
方法
利用范畴 zigzag 构造与提升性质重新表述项规范化,设计递归算法并证明其正确性。
评估
通过理论证明和多个实例展示算法,并说明其已作为 homotopy.io 证明助手的核心组件。
原文摘要(Abstract)

The theory of associative n-categories has recently been proposed as a strictly associative and unital approach to higher category theory. As a foundation for a proof assistant, this is potentially attractive, since it has the potential to allow simple formal proofs of complex high-dimensional algebraic phenomena. However, the theory relies on an implicit term normalisation procedure to recognize correct composites, with no recursive method available for computing it. Here we describe a new approach to term normalisation in associative n-categories, based on the categorical zigzag construction. This radically simplifies the theory, and yields a recursive algorithm for normalisation, which we prove is correct. Our use of categorical lifting properties allows us to give efficient proofs of our results. Our normalisation algorithm forms a core component of the proof assistant homotopy.io, and we illustrate our scheme with worked examples.

链接与引用

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

BibTeX
@inproceedings{HeidemannRV22,
  title = {Zigzag normalisation for associative n-categories},
  author = {Lukas Heidemann and David Reutter and Jamie Vicary},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533352}
}