论文标题
一阶逻辑及以后的片段的代数分类
Algebraic classifications for fragments of first-order logic and beyond
论文作者
论文摘要
逻辑的复杂性和可决定性是一个主要的研究领域，涉及大量不同的逻辑系统。这要求对该领域采用统一和系统的方法。我们介绍了一个基于代数方法的研究计划，以实现一阶逻辑（FO）及以后的碎片的复杂性分类。我们的基本系统GRA或一般关系代数与FO相当。它类似于圆柱代数，但只有七个不同的操作员使用有限的签名。我们通过限制允许的操作员集合获得的系统的可确定性和复杂性提供了全面的分类。我们还给出了最著名的FO片段的代数特征。此外，为了超越FO，我们介绍了广义操作员的概念，并简要研究了相关的系统。
Complexity and decidability of logics is a major research area involving a huge range of different logical systems. This calls for a unified and systematic approach for the field. We introduce a research program based on an algebraic approach to complexity classifications of fragments of first-order logic (FO) and beyond. Our base system GRA, or general relation algebra, is equiexpressive with FO. It resembles cylindric algebra but employs a finite signature with only seven different operators. We provide a comprehensive classification of the decidability and complexity of the systems obtained by limiting the allowed sets of operators. We also give algebraic characterizations of the best known decidable fragments of FO. Furthermore, to move beyond FO, we introduce the notion of a generalized operator and briefly study related systems.
