一句话：把位置策略的 universal graph 刻画推广到有限/无限记忆上界，并用 antichain 大小精确对应记忆量。
本文研究在可能无限的图上进行的无限持续时间博弈中，目标实现最优策略需要多少记忆。Ohlmann（LICS 2022）曾用 universal graphs 刻画位置策略，本文将该刻画推广到有限与无限记忆上界。作者引入 ε-memory（读到 ε-edge 时不能更新），证明允许 ε-memory 小于 m 的最优策略的目标，恰好对应反链大小受 m 限制的良基单调 universal graph；并用 universal structures 刻画 chromatic memory。结果覆盖有限及无限记忆界，如可数记忆策略。最后通过案例研究展示适用性，给出暴露局限的反例，并讨论闭包性质。
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.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@article{abs-2209-12044,
title = {Characterising memory in infinite games},
author = {Antonio Casares and Pierre Ohlmann},
journal = {Logical Methods in Computer Science},
volume = {Volume 21, Issue 1},
year = {2025},
doi = {10.46298/lmcs-21(1:28)2025}
}