paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Size-based termination of higher-order rewriting

基于 size 的高阶重写终止性
JFP vol.282018匹配度 2/10 · 该论文属于纯类型论与高阶重写终止性分析,与用户关注的 LLM/Agent 结合静态分析、浮点程序分析、贝叶斯程序分析等方向没有直接交集,仅在 PL/形式化验证基础层面有非常间接的联系。引用 4 inbox
FRÉDÉRIC BLANQUI
crossref: 2026-09-10

AI 速览

一句话:提出基于类型/大小分析的通用模块化准则,用于证明扩展用户重写规则的单型 λ 演算终止。

本文关注简单类型 λ 演算在加入由用户重写规则定义的函数符号后的终止性。受 Hughes、Pareto 与 Sabry 针对不动点算子和模式匹配函数的工作启发,既有准则常通过类型规则限制函数调用中参数的高度。作者将这一思路推广到基于重写定义的函数,并支持更一般的用户自定义 size 概念,给出通用且模块化的终止性判定准则。该成果为高阶重写系统的终止性证明提供了可组合的类型化方法;摘要未报告实现与实验评估。

问题
如何为带有用户自定义重写规则的简单类型 λ 演算建立通用、模块化的终止性判定准则。
方法
沿用基于 size 的类型化思路,用类型规则限制函数调用中参数的高度,并将其推广到重写定义与用户自定义 size 概念。
评估
以形式化准则及其通用性/模块性进行论证;摘要未提及具体实现或实验评估。
原文摘要(Abstract)

Abstract We provide a general and modular criterion for the termination of simply typed λ-calculus extended with function symbols defined by user-defined rewrite rules. Following a work of Hughes, Pareto and Sabry for functions defined with a fixpoint operator and pattern matching, several criteria use typing rules for bounding the height of arguments in function calls. In this paper, we extend this approach to rewriting-based function definitions and more general user-defined notions of size.

链接与引用

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

BibTeX
@article{paperbot336,
  title = {Size-based termination of higher-order rewriting},
  author = {FRÉDÉRIC BLANQUI},
  journal = {Journal of Functional Programming},
  volume = {28},
  year = {2018},
  doi = {10.1017/s0956796818000072}
}