We study FO+, a fragment of first-order logic on finite words, where monadic predicates can only appear positively. We show that there is a FO-definable language that is monotone in monadic predicates but not definable in FO+. This provides a simple proof that Lyndon's preservation theorem fails on finite structures. We additionally show that given a regular language, it is undecidable whether it is definable in FO+.


翻译:我们研究FO+,这是关于限值单词的第一阶逻辑的碎片, 其中monadic 的前提只能呈阳性。 我们显示有一种可定义的FO语言, 它在monadic 的前提中是单调的,但在FO+ 中是无法定义的。 这简单证明Lyndon的保存定理在有限结构上失败了。 我们还表明,根据一种常规语言,它能否在FO+ 中被定义是不可量化的。

0
下载
关闭预览

相关内容

【杜克-Bhuwan Dhingra】语言模型即知识图谱,46页ppt
专知会员服务
65+阅读 · 2021年11月15日
【干货书】机器学习速查手册,135页pdf
专知会员服务
125+阅读 · 2020年11月20日
【知识图谱@ACL2020】Knowledge Graphs in Natural Language Processing
专知会员服务
65+阅读 · 2020年7月12日
Keras François Chollet 《Deep Learning with Python 》, 386页pdf
专知会员服务
152+阅读 · 2019年10月12日
【新书】Python编程基础,669页pdf
专知会员服务
194+阅读 · 2019年10月10日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
已删除
将门创投
5+阅读 · 2017年11月20日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
3+阅读 · 2021年11月1日
Query Embedding on Hyper-relational Knowledge Graphs
Arxiv
4+阅读 · 2021年6月17日
Arxiv
7+阅读 · 2019年6月20日
Logic Rules Powered Knowledge Graph Embedding
Arxiv
7+阅读 · 2019年3月9日
Embedding Logical Queries on Knowledge Graphs
Arxiv
3+阅读 · 2019年2月19日
Logically-Constrained Reinforcement Learning
Arxiv
3+阅读 · 2018年12月6日
Arxiv
3+阅读 · 2018年2月24日
VIP会员
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
28+阅读 · 2019年5月18日
无监督元学习表示学习
CreateAMind
27+阅读 · 2019年1月4日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
已删除
将门创投
5+阅读 · 2017年11月20日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员