paperbot · PL 论文追踪

全部论文 待读 收藏

P2 Positional ω-regular languages

位置性 ω-正则语言
LICS Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science2024匹配度 2/10 · 该论文属于纯自动机理论与逻辑研究,讨论ω-正则语言的位置性判定与奇偶自动机刻画,与用户关注静态分析、LLM/Agent 交叉、浮点程序分析、贝叶斯程序分析等方向没有直接关联;仅与形式化验证有非常间接的理论联系。引用 0 inbox
Antonio Casares, Pierre Ohlmann
crossref: 2026-09-12dblp: 2026-09-12

AI 速览

一句话:通过刻画识别位置性语言的奇偶自动机,给出 ω-正则语言位置性的判定特征与封闭性结果。

论文研究图上双人博弈中语言的位置性:若以语言 L 为获胜目标时,主角总能只依赖当前位置选择最优策略,则 L 称为位置性的。作者通过刻画识别位置性语言的奇偶自动机,给出了 ω-正则语言位置性的完整特征。由此得到多个推论:位置性可在多项式时间内判定;该性质在有限到无限、单人到双玩家等情形下可提升;前缀无关的位置性目标类对并运算封闭;并在 ω-正则情形下回答了 Kopczyński 的猜想。

问题
研究 ω-正则语言作为图博弈获胜目标时,是否存在不依赖博弈历史的最优位置策略,并给出位置性的判定与结构刻画。
方法
描述识别位置性语言的奇偶自动机类,以此刻画 ω-正则语言的位置性,并推导有限到无限、单人到双玩家等提升及并封闭性。
评估
以理论证明和推论验证:得到位置性的多项式时间可判定性,证明前缀无关位置性目标对并封闭,并解决 Kopczyński 猜想在 ω-正则情形下的版本。
原文摘要(Abstract)

In the context of two-player games over graphs, a language L is called positional if, in all games using L as winning objective, the protagonist can play optimally using positional strategies, that is, strategies that do not depend on the history of the play. In this work, we describe the class of parity automata recognising positional languages, providing a characterisation of positionality for ω-regular languages. As corollaries, we establish decidability of positionality in polynomial time, finite-to-infinite and 1-to-2-players lifts, and show the closure under union of prefix-independent positional objectives, answering a conjecture by Kopczyński in the ω-regular case.

链接与引用

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

BibTeX
@inproceedings{CasaresO24,
  title = {Positional ω-regular languages},
  author = {Antonio Casares and Pierre Ohlmann},
  booktitle = {LICS},
  year = {2024},
  doi = {10.1145/3661814.3662087}
}