paperbot · PL 论文追踪

全部论文 待读 收藏

P2 A Hennessy-Milner Theorem for ATL with Imperfect Information

不完美信息 ATL 的 Hennessy-Milner 定理
LICS Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science2020匹配度 3/10 · 该论文研究 ATL 不完美信息下的 Hennessy-Milner 定理与互模拟不可判定性,属于形式逻辑与验证理论;与用户核心方向(LLM/Agent 结合静态分析、浮点程序分析、贝叶斯程序分析)无直接交集。仅在“形式化验证”这一宽泛兴趣上边缘相关,且不涉及 LLM、工程落地或程序分析工具。引用 1 inbox
Francesco Belardinelli, Catalin Dima, Vadim Malvone, Ferucio Tiplea
crossref: 2026-09-12

AI 速览

一句话:为不完美信息 ATL 建立基于历史的交替互模拟与共同知识语义之间的完整 Hennessy-Milner 定理,并证明相关互模拟不可判定。

本文研究不完美信息下交替时间时序逻辑(ATL)与交替互模拟之间的关系。作者提出带不完美信息的、基于历史的交替互模拟变体,并证明它能与采用共同知识语义的不完美信息 ATL 建立完整的 Hennessy-Milner 定理:两个模型在该互模拟下等价当且仅当它们满足相同的 ATL 公式。共同知识语义要求联盟实现目标所用的统一策略在联盟内部是共同知识。作者指出其他不完美信息 ATL 语义变体不能容纳该定理,并进一步证明两个有限不完美信息并发博弈结构(iCGS)之间存在基于历史的交替互模拟这一问题不可判定。

问题
如何为不完美信息 ATL 找到与之匹配的互模拟概念,使逻辑等价能够由互模拟刻画,即建立 Hennessy-Milner 定理?
方法
引入基于历史且带不完美信息的交替互模拟,采用要求联盟统一策略在联盟内为共同知识的 ATL 语义,给出完整 Hennessy-Milner 定理的证明,并分析该互模拟的判定问题。
评估
以理论证明为主要评估方式,证明所提互模拟与共同知识语义 ATL 的对应定理,并证明有限 iCGS 间该互模拟存在性不可判定。
原文摘要(Abstract)

We show that a history-based variant of alternating bisimulation with imperfect information allows it to be related to a variant of Alternating-time Temporal Logic (ATL) with imperfect information by a full Hennessy-Milner theorem. The variant of ATL we consider has a common knowledge semantics, which requires that the uniform strategy available for a coalition to accomplish some goal must be common knowledge inside the coalition, while other semantic variants of ATL with imperfect information do not accomodate a Hennessy-Milner theorem. We also show that the existence of a history-based alternating bisimulation between two finite Concurrent Game Structures with imperfect information (iCGS) is undecidable.

链接与引用

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

BibTeX
@inproceedings{paperbot5515,
  title = {A Hennessy-Milner Theorem for ATL with Imperfect Information},
  author = {Francesco Belardinelli and Catalin Dima and Vadim Malvone and Ferucio Tiplea},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394784}
}