论文标题
差异游戏，局部性和模型检查图的FO逻辑
Differential games, locality and model checking for FO logic of graphs
论文作者
论文摘要
我们介绍了用于图形逻辑的差异游戏，这是Ehrenfeucht-Fraïssé游戏的一种变体，其中游戏仅在一个图表上播放，并且两个玩家的动作都受到限制。我们证明，从某种意义上说，这些游戏足够强大，可以从无处可解释的图形类中捕获有关图形的基本信息。这与新介绍的差异局部性概念以及玩家对可能移动的限制使得在某些情况下确定游戏的获胜者变得很容易，这为FO模型检查问题提供了新的方法，以解释无处可密集的图形类别。
We introduce differential games for FO logic of graphs, a variant of Ehrenfeucht-Fraïssé games in which the game is played on only one graph and the moves of both players restricted. We prove that, in a certain sense, these games are strong enough to capture essential information about graphs from graph classes which are interpretable in nowhere dense graph classes. This, together with the newly introduced notion of differential locality and the fact that the restriction of possible moves by the players makes it easy to decide the winner of the game in some cases, leads to a new approach to the FO model checking problem on interpretations of nowhere dense graph classes.
