我的阅读状态 （保存写回仓库，全设备同步；首次保存需输入访问令牌）

AI 速览

一句话：引入 good-for-games ω-下推自动机，其非确定性可沿运行消解，从而支持与博弈、树及其他自动机组合。

论文引入了一类新的自动机——good-for-games ω-pushdown automata（ω-GFG-PDA）。这类自动机的非确定性可以仅依据目前已经构造出的运行来消解，而不依赖全局或未来信息。Good-for-gamenness 的关键优势在于可组合性：通常只有确定性自动机才能与博弈、树以及其他自动机进行组合，而 GFG 自动机在保留一定非确定性的同时具备类似确定性自动机的组合能力。作者给出了 ω-GFG-PDA 的概念定义，并说明该机制如何支持上述组合应用。该工作属于 ω-语言自动机与博弈理论交叉方向，为需要组合的 ω-下推语言识别提供了新工具。

问题

非确定自动机通常难以直接与博弈、树和其他自动机组合，除非先确定化；论文关注如何为 ω-下推自动机获得可沿已构造运行消解非确定性的 good-for-games 行为。

方法

定义 good-for-games ω-pushdown automata，其中非确定性的消解策略仅依赖目前已构造的运行，并利用该性质实现与博弈、树及其他自动机的组合。

评估

理论性工作，主要通过定义与可组合性论证说明 ω-GFG-PDA 的作用；摘要未报告实验评估。

链接与引用

DOI 原文 ·

@inproceedings{paperbot5530,
  title = {Good-for-games ω-Pushdown Automata},
  author = {Karoliina Lehtinen and Martin Zimmermann},
  booktitle = {LICS},
  year = {2020},
  doi = {10.1145/3373718.3394737}
}