paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Complete Game Logic with Sabotage

带破坏的完备博弈逻辑
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 1/10 · 该论文属于纯逻辑与自动机理论研究,关注带破坏的博弈逻辑 GLs 的表达力与 Hilbert 证明演算,与用户画像中的静态分析、LLM/Agent、浮点程序分析和贝叶斯程序分析均无直接关联。引用 5 inbox
Noah Abou El Wafa, André Platzer
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:提出带破坏的博弈逻辑 GLs,证明其表达力等价于模态 μ-演算,并给出完备的 Hilbert 证明演算。

论文在 Parikh 博弈逻辑基础上引入单一原语“设置陷阱/破坏”,得到带破坏的博弈逻辑 GLs,用于建模玩家可在游戏过程中改变规则的无限破坏博弈。作者证明 GLs 的表达力严格强于经典博弈逻辑,且恰好等价于模态 μ-演算,从而揭示模态不动点逻辑中的嵌套递归与破坏博弈中的对抗性动态规则变化之间的紧密联系。文中提出自然的 Hilbert 风格证明演算,并通过语法等表达性归约证明其完备性;作为推论,还得到 Parikh 博弈逻辑演算的一个简单扩展的完备性。

问题
如何以单一额外原语扩展 Parikh 博弈逻辑,以刻画玩家能在游戏过程中设置陷阱、改变规则的无限破坏博弈,并确定其表达力与完备证明系统。
方法
引入带破坏的博弈逻辑 GLs,利用语法等表达性归约证明其与模态 μ-演算等表达,并构造 Hilbert 风格证明演算来证明完备性。
评估
以理论证明方式给出表达力等价和演算完备性结果,并由此推出 Parikh 博弈逻辑的简单扩展的完备性。
原文摘要(Abstract)

Game logic with sabotage (GLs) is introduced as a simple and natural extension of Parikh's game logic with a single additional primitive, which allows players to lay traps for the opponent. GLs can be used to model infinite sabotage games, in which players can change the rules during game play. In contrast to game logic, which is strictly less expressive, GLs is exactly as expressive as the modal μ-calculus. This reveals a close connection between the entangled nested recursion inherent in modal fixpoint logics and adversarial dynamic rule changes characteristic for sabotage games. A natural Hilbert-style proof calculus for GLs is presented and proved complete using syntactic equiexpressiveness reductions. The completeness of a simple extension of Parikh's calculus for game logic follows.

链接与引用

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

BibTeX
@inproceedings{WafaP24,
  title = {Complete Game Logic with Sabotage},
  author = {Noah Abou El Wafa and André Platzer},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662121}
}