paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Star Games and Hydras

星游戏与九头蛇
LMCS vol.Volume 17, Issue 22021匹配度 1/10 · 该论文属于项重写与定理证明理论,虽与形式化验证有微弱关联,但不涉及LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,也不符合用户对工业落地、问题驱动或LLM工具改进的偏好。引用 0 inbox
Jörg Endrullis, Jan Willem Klop, Roy Overbeek
crossref: 2026-09-10

AI 速览

一句话:提出星游戏,用树上的简单规则直接证明重写终止性,并给出 Hydra 战斗的无序数证明。

递归路径序是项重写中证明终止性的关键工具。本文重新表述递归路径序:在树或项上引入星号控制符号,表示将被定义的序中该树变小的命令,由此得到星游戏。星游戏为许多重写任务的终止性证明提供了方便框架。作者表明,即使在有限无标号树上使用最简单的星游戏,也能直接证明著名 Hydra 战斗的终止性,且无需提及序数。文章还给出建立星游戏的另一条路线,基于 Buchholz 的证明方法(经 van Oostrom 改编),得到星控制符号的定量版本。最后提出若干问题与未来方向。

问题
如何在项重写中更直接、无需序数地证明终止性,尤其是 Hydra 战斗等复杂重写系统。
方法
用树或项上的星号控制规则构造星游戏,并借助 Buchholz 经 van Oostrom 改编的方法得到定量版本。
评估
通过给出 Hydra 战斗终止性的直接证明,以及星游戏在多类重写任务中的适用性来论证方法。
原文摘要(Abstract)

The recursive path ordering is an established and crucial tool in term rewriting to prove termination. We revisit its presentation by means of some simple rules on trees (or corresponding terms) equipped with a 'star' as control symbol, signifying a command to make that tree (or term) smaller in the order being defined. This leads to star games that are very convenient for proving termination of many rewriting tasks. For instance, using already the simplest star game on finite unlabeled trees, we obtain a very direct proof of termination of the famous Hydra battle, direct in the sense that there is not the usual mention of ordinals. We also include an alternative road to setting up the star games, using a proof method of Buchholz, adapted by van Oostrom, resulting in a quantitative version of the star as control symbol. We conclude with a number of questions and future research directions.

链接与引用

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

BibTeX
@article{paperbot1307,
  title = {Star Games and Hydras},
  author = {Jörg Endrullis and Jan Willem Klop and Roy Overbeek},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 17, Issue 2},
  year = {2021},
  doi = {10.23638/lmcs-17(2:20)2021}
}