paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Deciding All Behavioral Equivalences at Once: A Game for Linear-Time--Branching-Time Spectroscopy

一次性判定所有行为等价:线性时间—分支时间谱系中的博弈
LMCS vol.Volume 18, Issue 32022匹配度 2/10 · 该论文属于进程代数与行为等价博弈的纯形式语义研究,虽与形式化验证相关,但未涉及 LLM/Agent、静态分析、浮点程序分析或贝叶斯程序分析,与用户画像的核心交叉方向几乎无重合。引用 5 inbox
Benjamin Bisping, David N. Jansen, Uwe Nestmann
crossref: 2026-09-10

AI 速览

一句话:提出统一博弈,可在 van Glabbeek 线性时间—分支时间谱系中一次性判定两进程的行为等价关系。

论文研究有限状态进程之间的行为等价判定:van Glabbeek 的线性时间—分支时间谱系包含多种粗细不同的等价与前序,传统方法需逐一判定。作者推广了互模拟博弈,使其能从该谱系中每个有限、对子公式封闭的逻辑片段中构造出区分两进程的 Hennessy–Milner 逻辑公式。他们识别了刻画表达力的关键维度,从而保证所得公式属于能够区分两进程的最粗行为前序或等价。作者进一步证明,由该博弈诱导的算法能够一次性确定一对进程在谱系中各等价关系上的最佳匹配,即精确判断它们在哪些(不)等价下相同或不同。

问题
如何一次性判定有限状态进程在一整族线性时间—分支时间行为等价/前序中的关系,并找到最粗的区分性等价。
方法
推广互模拟博弈,从谱系中每个有限且子公式封闭的 Hennessy–Milner 逻辑片段生成区分公式,并刻画决定表达力的关键维度。
评估
通过理论证明说明:所诱导的算法能够确定一对进程在谱系中各等价关系上的最佳匹配,即判断哪些等价成立、哪些被区分。
原文摘要(Abstract)

We introduce a generalization of the bisimulation game that finds distinguishing Hennessy-Milner logic formulas from every finitary, subformula-closed language in van Glabbeek's linear-time--branching-time spectrum between two finite-state processes. We identify the relevant dimensions that measure expressive power to yield formulas belonging to the coarsest distinguishing behavioral preorders and equivalences; the compared processes are equivalent in each coarser behavioral equivalence from the spectrum. We prove that the induced algorithm can determine the best fit of (in)equivalences for a pair of processes.

链接与引用

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

BibTeX
@article{paperbot1668,
  title = {Deciding All Behavioral Equivalences at Once: A Game for Linear-Time--Branching-Time Spectroscopy},
  author = {Benjamin Bisping and David N. Jansen and Uwe Nestmann},
  journal = {Logical Methods in Computer Science},
  volume = {Volume 18, Issue 3},
  year = {2022},
  doi = {10.46298/lmcs-18(3:19)2022}
}