paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Lean and full congruence formats for recursion

递归的 lean 与 full 同余格式
LICS 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)2017匹配度 1/10 · 该论文研究进程代数中递归的同余格式与结构操作语义(ntyft/ntyxt、tyft/tyxt),属于并发与形式语义的理论工作;与用户关注的静态分析、LLM/Agent、浮点程序分析及贝叶斯程序分析均无直接关联。引用 12 inbox
Rob van Glabbeek
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:区分递归的精简与完全同余,证明 bisimilarity 在 ntyft/ntyxt 下满足 lean 同余,在 tyft/tyxt 下满足 full 同余。

本文研究带递归构造的进程描述语言中语义等价与预序的同余性质。作者区分两种要求:lean 同余只允许将进程的封闭子表达式替换为等价项;full 同余还允许在递归规约内部替换可能含外部绑定递归变量的子表达式。通过结构操作语义(SOS)的 ntyft/ntyxt 与 tyft/tyxt 格式,论文证明 bisimilarity 对所有 ntyft/ntyxt 语言是递归的 lean(预)同余,并在更强的 tyft/tyxt 格式下成为 full 同余。结果明确了递归替换下的同余边界,为进程演算语义格式提供了统一定理。

问题
带递归构造的进程语言中,语义等价或预序在替换下何时保持同余,尤其是递归规约内部含绑定递归变量的子表达式能否被等价替换。
方法
区分 lean 同余与 full 同余两种要求,并在结构操作语义的 ntyft/ntyxt 与 tyft/tyxt 格式下分析 bisimilarity 的同余性质。
评估
以理论证明的方式给出结论:bisimilarity 对所有 ntyft/ntyxt 语言是递归的 lean(预)同余,对 tyft/tyxt 语言是 full 同余。
原文摘要(Abstract)

In this paper I distinguish two (pre)congruence requirements for semantic equivalences and preorders on processes given as closed terms in a system description language with a recursion construct. A lean congruence preserves equivalence when replacing closed subexpressions of a process by equivalent alternatives. A full congruence moreover allows replacement within a recursive specification of subexpressions that may contain recursion variables bound outside of these subexpressions. I establish that bisimilarity is a lean (pre)congruence for recursion for all languages with a structural operational semantics in the ntyft/ntyxt format. Additionally, it is a full congruence for the tyft/tyxt format.

链接与引用

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

BibTeX
@inproceedings{Glabbeek17b,
  title = {Lean and full congruence formats for recursion},
  author = {Rob van Glabbeek},
  booktitle = {LICS},
  year = {2017},
  doi = {10.1109/lics.2017.8005142}
}