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,我们引入了通用操作员的概念,并简要研究相关系统。

0
下载
关闭预览

相关内容

**2016年年度应用** * 无需锻炼设备,每天只需几分钟时间 * 趣味成就和奖励不断鼓励你 * 基于《纽约时报杂志》报道的7分钟科学锻炼文章
专知会员服务
52+阅读 · 2020年9月7日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
CSKG: The CommonSense Knowledge Graph
Arxiv
18+阅读 · 2020年12月21日
Arxiv
101+阅读 · 2020年3月4日
Embedding Logical Queries on Knowledge Graphs
Arxiv
5+阅读 · 2018年9月6日
Arxiv
3+阅读 · 2017年12月14日
VIP会员
相关VIP内容
专知会员服务
52+阅读 · 2020年9月7日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
CCF C类 | DSAA 2019 诚邀稿件
Call4Papers
6+阅读 · 2019年5月13日
计算机 | CCF推荐期刊专刊信息5条
Call4Papers
3+阅读 · 2019年4月10日
IEEE | DSC 2019诚邀稿件 (EI检索)
Call4Papers
10+阅读 · 2019年2月25日
人工智能 | SCI期刊专刊信息3条
Call4Papers
5+阅读 · 2019年1月10日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
【今日新增】IEEE Trans.专刊截稿信息8条
Call4Papers
7+阅读 · 2017年6月29日
Top
微信扫码咨询专知VIP会员