paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Temporal Team Semantics Revisited

时序团队语义再探
LICS Proceedings of the 37th Annual ACM/IEEE Symposium on Logic in Computer Science2022匹配度 2/10 · 论文属于纯逻辑/形式语义与异步 hyperproperty 可判定性研究,与用户核心方向(LLM/Agent 与静态分析、形式化验证交叉,浮点/贝叶斯程序分析)几乎没有交集;仅在“形式化验证/逻辑”大领域上略有邻近,但不涉及 LLM、程序分析或工业落地内容。引用 13 inbox
Jens Oliver Gutsfeld, Arne Meier, Christoph Ohrem, Jonni Virtema
crossref: 2026-09-12dblp: 2026-09-12arxiv: 2026-09-12

AI 速览

一句话:重新审视时序团队语义,提出三种量化时间求值函数的异步 hyperproperty 逻辑,并分析其可判定性。

论文重新考察时序团队语义的基础,以处理异步 hyperproperties。作者定义三种逻辑,它们通过加入对所谓时间求值函数(time evaluation functions)的量化来控制迹的异步推进。论文把同步逻辑嵌入新逻辑,并证明带布尔析取的相关逻辑的模型检测问题高度不可判定,证明方法为编码非确定性 2-counter 机的循环计算。最后,作者给出到交替异步 Büchi 自动机的翻译,得到路径检测问题的可判定性,以及受限模型检测与可满足性问题的可判定性。该工作把异步 hyperproperties 的逻辑刻画与自动机方法联系起来。

问题
研究异步 hyperproperties 的逻辑基础,尤其是如何用时序团队语义刻画迹的异步推进。
方法
定义三种加入时间求值函数量化的逻辑,建立同步逻辑到新逻辑的嵌入,并用非确定性 2-counter 机编码和交替异步 Büchi 自动机翻译进行分析。
评估
理论证明:相关逻辑的模型检测高度不可判定;路径检测问题可判定,受限模型检测与可满足性也可判定。
原文摘要(Abstract)

In this paper, we study a novel approach to asynchronous hyperproperties by reconsidering the foundations of temporal team semantics. We consider three logics: , and , which are obtained by adding quantification over so-called time evaluation functions controlling the asynchronous progress of traces. We then relate synchronous to our new logics and show how it can be embedded into them. We show that the model checking problem for with Boolean disjunctions is highly undecidable by encoding recurrent computations of non-deterministic 2-counter machines. Finally, we present a translation from to Alternating Asynchronous Büchi Automata and obtain decidability results for the path checking problem as well as restricted variants of the model checking and satisfiability problems.

链接与引用

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

BibTeX
@inproceedings{GutsfeldMOV22,
  title = {Temporal Team Semantics Revisited},
  author = {Jens Oliver Gutsfeld and Arne Meier and Christoph Ohrem and Jonni Virtema},
  booktitle = {LICS},
  year = {2022},
  doi = {10.1145/3531130.3533360}
}