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
下载
关闭预览

相关内容

元学习与图神经网络逻辑推导,55页ppt
专知会员服务
128+阅读 · 2020年4月25日
开源书:PyTorch深度学习起步
专知会员服务
50+阅读 · 2019年10月11日
[综述]深度学习下的场景文本检测与识别
专知会员服务
77+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
已删除
将门创投
3+阅读 · 2019年4月19日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
A unifying point of view on expressive power of GNNs
Arxiv
0+阅读 · 2021年6月17日
Arxiv
0+阅读 · 2021年6月16日
Arxiv
0+阅读 · 2021年6月16日
Arxiv
0+阅读 · 2021年6月15日
Arxiv
0+阅读 · 2021年6月15日
Arxiv
5+阅读 · 2018年4月22日
VIP会员
相关资讯
ICLR2019最佳论文出炉
专知
12+阅读 · 2019年5月6日
已删除
将门创投
3+阅读 · 2019年4月19日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
Disentangled的假设的探讨
CreateAMind
9+阅读 · 2018年12月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
计算机视觉近一年进展综述
机器学习研究会
9+阅读 · 2017年11月25日
【学习】Hierarchical Softmax
机器学习研究会
4+阅读 · 2017年8月6日
Top
微信扫码咨询专知VIP会员