On Winning Ehrenfeucht Games and Monadic NP
On Winning Ehrenfeucht Games and Monadic NP
复制标题
论赢得 Ehrenfeucht 游戏和 Monadic NP
DOI：
10.1016/0168-0072(95)00030-5
复制
发表时间：
1996
影响因子：
0.6
通讯作者：
T. Schwentick
中科院分区：
文献类型：
--
作者：
T. Schwentick
有限模型理论中的不可表达性结果通常通过证明复制者（Escherichfeucht博弈的两个参与者之一）在某些结构上具有获胜策略来证明。本文介绍了一种新的方法，它允许在一定条件下，复制器在两个有限结构的一些小部分上的获胜策略扩展为全局擦除策略。
Inexpressibility results in Finite Model Theory are often proved by showing that Duplicator, one of the two players of an Ehrenfeucht game, has a winning strategy on certain structures. In this article a new method is introduced that allows, under certain conditions, the extension of a winning strategy of Duplicator on some small parts of two finite structures to a global wiping strategy.