跳到正文
研踪PaperTrail
← 研踪 PaperTrail

arXiv:2310.06121 · v4

From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting

首次提交 2023-10-10 03:56
版本更新 2026-11-19 19:07
雷达观测 2026-11-20 19:57
arXiv ↗PDF ↗

摘要

There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems (PTRSs). These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool AProVE.

期刊信息:Proc. FoSSaCS 2024, LNCS 14575, pp. 206-228, Springer, 2024

AI 论文解读

基于摘要 · 非全文审阅

此版本尚未生成 AI 解读。解读由后台任务生成并按论文版本保存,登录后共享已有结果。

版本差异

本站首次收录为 v4,暂无更早版本可对照。

观测到的版本

相邻记录可能跳过中间版本;首次发现 v2 及以上也会标为版本更新。

v4 · 2026-11-19 19:07 · 最新观测版本

From Innermost to Full Almost-Sure Termination of Probabilistic Term Rewriting

There are many evaluation strategies for term rewrite systems, but proving termination automatically is usually easiest for innermost rewriting. Several syntactic criteria exist when innermost termination implies full termination. We adapt these criteria to the probabilistic setting, e.g., we show when it suffices to analyze almost-sure termination (AST) w.r.t. innermost rewriting to prove full AST of probabilistic term rewrite systems (PTRSs). These criteria also apply to other notions of termination like positive AST. We implemented and evaluated our new contributions in the tool AProVE.

查看此版本解读 →查看此版本原文 ↗