Generalized quantifiers and pebble games on finite structures
Generalized quantifiers and pebble games on finite structures
复制标题
有限结构上的广义量词和卵石博弈
DOI：
10.1109/lics.1992.185547
复制
发表时间：
1992
期刊：
影响因子：
--
通讯作者：
J. Väänänen
中科院分区：
文献类型：
--
作者：
Phokion G. Kolaitis;J. Väänänen
研究了有限结构领域中的广义量词，并与无限的逻辑L /subsubine Infinity Omega // SUP Omega /相结合，以获得可用于表达原始逻辑中无法定义的多项式时间属性的新逻辑。结果表明，有限结构相对于新逻辑的等效性可以通过某些是Ehrenfeucht-Fraisse游戏的变体来表征。此时间理论的表征与复杂的组合工具相结合，以研究有限模型理论中广义量词的范围和限制。<< etx >>
Generalized quantifiers in the realm of finite structures are studied and combined with an infinitary logic L/sub infinity omega //sup omega / to obtain new logics that can be used to express polynomial-time properties that are not definable in the original logic. It is shown that equivalence of finite structures relative to the new logics can be characterized in terms of certain pebble games that are a variant of the Ehrenfeucht-Fraisse games. This time-theoretic characterization is combined with sophisticated combinatorial tools in order to investigate the scopes and limits of generalized quantifiers in finite model theory.<<ETX>>