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.
翻译:逻辑的复杂性和易变性是一个涉及多种不同逻辑系统的重要研究领域,这要求对实地采取统一和系统的方法。我们引入了一个基于代数方法的研究方案,对一级逻辑(FO)和以后的碎片的复杂分类进行代谢。我们的基础系统GRA或一般关系代数与FO相当。它类似于细胞代数,但只使用7个不同的操作员的有限特征。我们对通过限制允许操作员获得的系统的易变性和复杂性进行了全面分类。我们还对FO最已知的可变分数碎片进行了代数定性。此外,为了超越FO,我们引入了通用操作员的概念,并简要研究相关系统。