论文标题
表征无限游戏中的记忆
Characterising memory in infinite games
论文作者
论文摘要
本文关注的是在潜在的无限图上玩的无限持续时间。最近，Ohlmann（LICS 2022）通过通用图提出了一种目标的特征，即通用图形：当且仅当它接收有序良好的单调通用图时，目标才是位置。我们将Ohlmann的特征扩展到包含（有限或无限）内存上限。我们证明，目的是在$ \ varepsilon $ -MEMORY少于$ M $（阅读$ \ varepsilon $ -EDDED时无法更新的内存）中，目标是允许有良好的单调通用图，其抗小节具有$ m $ bugn的尺寸。我们还通过适当的通用结构对色度记忆进行表征。我们的结果适用于有限的和无限的内存范围（例如，具有有限但无限内存的目标或具有可数的内存策略的目标）。我们通过进行一些案例研究来说明我们的框架的适用性，我们提供了目睹方法局限性的示例，并讨论了从结果随之而来的一般封闭属性。
This paper is concerned with games of infinite duration played over potentially infinite graphs. Recently, Ohlmann (LICS 2022) presented a characterisation of objectives admitting optimal positional strategies, by means of universal graphs: an objective is positional if and only if it admits well-ordered monotone universal graphs. We extend Ohlmann's characterisation to encompass (finite or infinite) memory upper bounds. We prove that objectives admitting optimal strategies with $\varepsilon$-memory less than $m$ (a memory that cannot be updated when reading an $\varepsilon$-edge) are exactly those which admit well-founded monotone universal graphs whose antichains have size bounded by $m$. We also give a characterisation of chromatic memory by means of appropriate universal structures. Our results apply to finite as well as infinite memory bounds (for instance, to objectives with finite but unbounded memory, or with countable memory strategies). We illustrate the applicability of our framework by carrying out a few case studies, we provide examples witnessing limitations of our approach, and we discuss general closure properties which follow from our results.
