一句话：提出通用图理论，统一构造无限时长博弈的值迭代算法，并改进奇偶与平均收益博弈的时空复杂度。
本文研究无限时长博弈（如奇偶博弈与平均收益博弈）的求解算法，提出“通用图”这一构造性工具。第一部分建立通用图理论，证明近期若干相关模型之间的等价性与规范化结果，并为任何位置确定的目标构造通用值迭代算法。第二部分给出四个应用：奇偶博弈、平均收益博弈、奇偶目标与平均收益目标的析取，以及多个平均收益目标的析取。对每种情形，作者构造的算法在时间与空间复杂度上达到或优于已知最佳结果，表明通用图可作为设计无限时长博弈算法的统一框架。
We introduce the notion of universal graphs as a tool for constructing algorithms solving games of infinite duration such as parity games and mean payoff games. In the first part we develop the theory of universal graphs, with two goals: showing an equivalence and normalisation result between different recently introduced related models, and constructing generic value iteration algorithms for any positionally determined objective. In the second part we give four applications: to parity games, to mean payoff games, to a disjunction between a parity and a mean payoff objective, and to disjunctions of several mean payoff objectives. For each of these four cases we construct algorithms achieving or improving over the best known time and space complexity.
@article{paperbot1658,
title = {The Theory of Universal Graphs for Infinite Duration Games},
author = {Thomas Colcombet and Nathanaël Fijalkow and Paweł Gawrychowski and Pierre Ohlmann},
journal = {Logical Methods in Computer Science},
volume = {Volume 18, Issue 3},
year = {2022},
doi = {10.46298/lmcs-18(3:29)2022}
}