Game-based notions of locality over finite models
Game-based notions of locality over finite models
复制标题
有限模型上基于博弈的局部性概念
DOI：
10.1016/j.apal.2007.11.012
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
Arenas M
中科院分区：
文献类型：
--
作者：
Arenas M
逻辑中的局部性概念说，公式的真值可以通过查看其自由变量的小邻域的同构类型来局部确定。事实证明，这些概念在许多应用中都很有用。然而，它们都指的是邻域的同构，这是大多数局部逻辑无法测试的。一种更强烈的地方性概念认为，公式的真值取决于逻辑本身对那个小社区的看法。由于许多逻辑的表现力可以用游戏来表征，也可以说公式的真值是由关于游戏的那个小邻域的类型来决定的。这种基于博弈的局部性概念通常可以在传统的基于同构的局部性概念不能应用的情况下应用。我们的目标是研究基于游戏的位置概念。我们使用游戏的抽象视图，将游戏包含在许多逻辑中。我们来看三个逐渐复杂的地方性概念。最简单的游戏只需要非常温和的条件，并且适用于大多数感兴趣的逻辑。基于汉夫和盖夫曼定理的其他概念需要更多的限制。我们陈述了这些限制，并给出了满足和不满足各自基于博弈的局部性概念的逻辑示例。
Locality notions in logic say that the truth value of a formula can be determined locally, by looking at the isomorphism type of a small neighbourhood of its free variables. Such notions have proved to be useful in many applications. They all, however, refer to isomorphisms of neighbourhoods, which most local logics cannot test. A stronger notion of locality says that the truth value of a formula is determined by what the logic itself can say about that small neighbourhood. Since the expressiveness of many logics can be characterized by games, one can also say that the truth value of a formula is determined by the type, with respect to a game, of that small neighbourhood. Such game-based notions of locality can often be applied when traditional isomorphism-based notions of locality cannot. Our goal is to study game-based notions of locality. We work with an abstract view of games that subsumes games for many logics. We look at three, progressively more complicated locality notions. The easiest requires only very mild conditions on the game and works for most logics of interest. The other notions, based on Hanf’s and Gaifman’s theorems, require more restrictions. We state those restrictions and give examples of logics that satisfy and fail the respective game-based notions of locality.
登录
查看更多内容
描述性复杂性和有限模型
DOI：
10.1090/dimacs/031
发表时间：
1997
期刊：
SIAM J. Comput.
影响因子：
--
作者：
N. Immerman;Phokion G. Kolaitis
通讯作者：
Phokion G. Kolaitis
有限结构上的广义量词和卵石博弈
DOI：
10.1109/lics.1992.185547
发表时间：
1992
期刊：
[1992] Proceedings of the Seventh Annual IEEE Symposium on Logic in Computer Science
影响因子：
--
作者：
Phokion G. Kolaitis;J. Väänänen
通讯作者：
J. Väänänen
DOI：
10.46298/dmtcs.254
发表时间：
1998-02
期刊：
Discret. Math. Theor. Comput. Sci.
影响因子：
--
作者：
T. Schwentick;Klaus Barthelmann
通讯作者：
T. Schwentick;Klaus Barthelmann
DOI：
10.1145/1055558.1055592
发表时间：
2004-06
期刊：
Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems
影响因子：
--
作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
通讯作者：
M. Arenas;P. Barceló;Ronald Fagin;L. Libkin
复杂性理论回顾二
DOI：
10.1007/978-1-4612-1872-2
发表时间：
1998
期刊：
Theor. Comput. Sci.
影响因子：
--
作者：
L. Hemaspaandra;A. Selman
通讯作者：
A. Selman