Implicit Definability and Infinitary Logic in Finite Model Theory
Implicit Definability and Infinitary Logic in Finite Model Theory
复制标题
有限模型理论中的隐式可定义性和无限逻辑
DOI：
--
复制
发表时间：
1995
期刊：
影响因子：
--
通讯作者：
Phokion G. Kolaitis
中科院分区：
文献类型：
--
作者：
A. Dawar;L. Hella;Phokion G. Kolaitis
本文研究了有限结构上多变量无穷逻辑L ∞ω ω与L ∞ω ω有效片段的隐可定义性之间的关系。我们表明，不动点逻辑严格低于一阶隐式可定义的表达能力。我们还建立了不动点逻辑从一阶隐可定义性到L ∞ω ω的某种限制的分离等价于PTIME从UP ω ω-UP的分离。最后，我们描述了有限结构上的部分不动点逻辑和部分不动点逻辑中的隐可定义性之间的关系。
We study the relationship between the infinitary logic L ∞ω ω with finitely many variables and implicit definability in effective fragments of L ∞ω ω on finite structures. We show that fixpoint logic has strictly less expressive power than first-order implicit definability. We also establish that the separation of fixpoint logic from a certain restriction of first-order implicit definability to L ∞ω ω is equivalent to the separation of PTIME from UP ∩ co-UP. Finally, we delineate the relationship between partial fixpoint logic and implicit definability in partial fixpoint logic on finite structures.