paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Homological Invariants of Higher-Order Equational Theories

高阶等式理论的同调不变量
LICS 2025 40th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2025匹配度 1/10 · 论文属于纯形式语义/类型论,研究高阶等式理论的同调不变量与公理数量下界,与用户关注的静态分析、LLM/Agent、浮点程序分析或贝叶斯程序分析均无直接交集。引用 1 inbox
Mirai Ikebuchi
crossref: 2026-09-12

AI 速览

一句话:将同调方法推广到高阶等式理论,用同调群计算等式公理数量的下界。

该论文研究高阶等式理论的公理最小化问题。已有工作表明,对群、布尔代数等一阶等式理论,同调方法可给出公理数量下界。作者将这一结果推广到高阶情形:考虑带积类型和单位类型的简单类型λ演算,研究λ项之间等式构成的集合。论文定义给定等式理论的同调群,并证明可由这些同调群计算该理论所需等式数量的下界。结果属于理论层面的贡献,未涉及实现或实验评估。

问题
如何为高阶等式理论(特别是带积与单位类型的简单类型λ演算中的等式集合)获得公理数量下界。
方法
定义等式理论的同调群,将一阶同调下界结果推广到高阶,并由同调群推导所需等式数量的下界。
评估
通过数学构造与证明给出理论结果;摘要未报告实现或实验评估。
原文摘要(Abstract)

Many first-order equational theories, such as the theory of groups or boolean algebras, can be presented by a smaller set of axioms than the original one. Recent studies showed that a homological approach to equational theories gives us inequalities to obtain lower bounds on the number of axioms.In this paper, we extend this result to higher-order equational theories. More precisely, we consider simply typed lambda calculus with product and unit types and study sets of equations between lambda terms. Then, we define homology groups of the given equational theory and show that a lower bound on the number of equations can be computed from the homology groups.

链接与引用

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

BibTeX
@inproceedings{paperbot8668,
  title = {Homological Invariants of Higher-Order Equational Theories},
  author = {Mirai Ikebuchi},
  booktitle = {LICS},
  year = {2025},
  doi = {10.1109/lics65433.2025.00024}
}