Almost Everywhere Equivalence of Logics in Finite Model Theory
Almost Everywhere Equivalence of Logics in Finite Model Theory
复制标题
有限模型理论中逻辑几乎处处等价
DOI：
--
复制
发表时间：
1996
影响因子：
0.6
通讯作者：
Kerkko Luosto
中科院分区：
文献类型：
--
作者：
L. Hella;Phokion G. Kolaitis;Kerkko Luosto
摘要本文介绍了一种新的框架，用于对有限结构上的逻辑进行分类，并研究它们的表达能力。这个框架是基于逻辑的几乎处处等价的概念，也就是说，两个逻辑在一类渐近测度1上具有相同的表达能力。更精确地说，如果L，L′是两个逻辑，μ是有限结构上的渐近测度，则L ∈ a.e. L′（μ）表示存在一个有限结构类C，μ（C）= 1，并且使得L和L′在C上定义相同的查询。我们进行了系统的调查。关于统一的措施，并分析了E.A. -等价类的几个逻辑已被广泛研究的有限模型理论。此外，我们还探索了与描述复杂性理论的联系，并在这个新框架的背景下考察了模型论某些经典结果的地位。
Abstract We introduce a new framework for classifying logics on finite structures and studying their expressive power. This framework is based on the concept of almost everywhere equivalence of logics, that is to say, two logics having the same expressive power on a class of asymptotic measure 1. More precisely, if L, L′ are two logics and μ is an asymptotic measure on finite structures, then L ≡a.e. L′ (μ) means that there is a class C of finite structures with μ(C) = 1 and such that L and L′ define the same queries on C. We carry out a systematic investigation of ≡a.e. with respect to the uniform measure and analyze the ≡a.e.-equivalence classes of several logics that have been studied extensively in finite model theory. Moreover, we explore connections with descriptive complexity theory and examine the status of certain classical results of model theory in the context of this new framework.