The finite models of a universal sentence $\Phi$ in a finite relational signature are the age of a structure if and only if $\Phi$ has the joint embedding property. We prove that the computational problem whether a given universal sentence $\Phi$ has the joint embedding property is undecidable, even if $\Phi$ is additionally Horn and the signature of $\Phi$ only contains relation symbols of arity at most two.


翻译:在有限关系签名中通用判决$\Phi$的有限模式是一个结构的年龄,只要$\Phi$有共同嵌入的财产。 我们证明,一个特定通用判决$\Phi$是否拥有共同嵌入财产的计算问题无法确定,即使$\Phi$是额外的,而$\Phi$的签名最多只包含两个等同关系符号。

0
下载
关闭预览

相关内容

人类接受高层次教育、进行原创性研究的场所。 现在的大学一般包括一个能授予硕士和博士学位的研究生院和数个专业学院,以及能授予学士学位的一个本科生院。大学还包括高等专科学校
专知会员服务
315+阅读 · 2020年11月24日
因果图,Causal Graphs,52页ppt
专知会员服务
247+阅读 · 2020年4月19日
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
论文浅尝 | EARL: Joint Entity and Relation Linking for QA over KG
开放知识图谱
6+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
自然语言处理 (三) 之 word embedding
DeepLearning中文论坛
19+阅读 · 2015年8月3日
Arxiv
0+阅读 · 2022年1月14日
Logic Rules Powered Knowledge Graph Embedding
Arxiv
7+阅读 · 2019年3月9日
VIP会员
相关主题
相关VIP内容
专知会员服务
315+阅读 · 2020年11月24日
因果图,Causal Graphs,52页ppt
专知会员服务
247+阅读 · 2020年4月19日
相关资讯
内涵网络嵌入:Content-rich Network Embedding
我爱读PAMI
4+阅读 · 2019年11月5日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
论文浅尝 | EARL: Joint Entity and Relation Linking for QA over KG
开放知识图谱
6+阅读 · 2018年10月30日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
Linguistically Regularized LSTMs for Sentiment Classification
黑龙江大学自然语言处理实验室
8+阅读 · 2018年5月4日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
自然语言处理 (三) 之 word embedding
DeepLearning中文论坛
19+阅读 · 2015年8月3日
Top
微信扫码咨询专知VIP会员