Anti-unification in logic programming refers to the process of capturing common syntactic structure among given goals, computing as such a single new goal that is more general and hence called a generalization of the given goals. Finding an arbitrary common generalization for two goals is trivial, but looking for those common generalizations that are either as large as possible (called largest common generalizations) or as specific as possible (called most specific generalizations) is a non-trivial optimization problem, in particular when goals are considered to be unordered sets of atoms. In this work we provide an in-depth study of the problem by defining two different generalization relations. We formulate a characterization of what constitutes a most specific generalization in both settings. While these generalizations can be computed in polynomial time, we show that when the number of variables in the generalization needs to be minimized, the problem becomes NP-hard. We subsequently revisit an abstraction of the largest common generalization when anti-unification is based on injective variable renamings, and prove that it can be computed in polynomially bounded time.


翻译:在逻辑编程中,反统一是指在特定目标中捕捉共同综合结构的过程,将这种单一的新目标计算成比较一般的、因而称为对特定目标的概括性。为两个目标寻找任意的通用概括性是微不足道的,但寻找那些尽可能大(所谓的最大共同概括性)或尽可能具体(所谓的最具体的概括性)的通用性,是一个非三重优化问题,特别是当目标被视为没有顺序的原子时。在这项工作中,我们通过界定两种不同的概括性关系,对问题进行深入研究。我们对两种情况下最具体的概括性进行定性。虽然这些概括性可以在多数值时间内计算,但我们表明,当一般化中变量的数量需要尽可能小时,问题就会变得难以解决。当反统一性的目标被认为是没有顺序的一组原子时,我们随后重新审视了最大共同的抽象性一般化的抽象性,因为反统一性是以预言的变量重新命名为基础,并证明它可以在多数值约束的时间内进行计算。

0
下载
关闭预览

相关内容

专知会员服务
161+阅读 · 2020年1月16日
《DeepGCNs: Making GCNs Go as Deep as CNNs》
专知会员服务
30+阅读 · 2019年10月17日
机器学习入门的经验与建议
专知会员服务
92+阅读 · 2019年10月10日
【哈佛大学商学院课程Fall 2019】机器学习可解释性
专知会员服务
103+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
最新BERT相关论文清单,BERT-related Papers
专知会员服务
52+阅读 · 2019年9月29日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Arxiv
14+阅读 · 2020年12月17日
Arxiv
6+阅读 · 2019年12月30日
Knowledge Distillation from Internal Representations
Arxiv
4+阅读 · 2019年10月8日
Arxiv
11+阅读 · 2018年7月31日
Arxiv
10+阅读 · 2018年3月22日
VIP会员
相关VIP内容
相关资讯
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
动物脑的好奇心和强化学习的好奇心
CreateAMind
10+阅读 · 2019年1月26日
强化学习的Unsupervised Meta-Learning
CreateAMind
17+阅读 · 2019年1月7日
Unsupervised Learning via Meta-Learning
CreateAMind
42+阅读 · 2019年1月3日
meta learning 17年:MAML SNAIL
CreateAMind
11+阅读 · 2019年1月2日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
17+阅读 · 2018年12月24日
【NIPS2018】接收论文列表
专知
5+阅读 · 2018年9月10日
Hierarchical Disentangled Representations
CreateAMind
4+阅读 · 2018年4月15日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
【论文】图上的表示学习综述
机器学习研究会
14+阅读 · 2017年9月24日
Top
微信扫码咨询专知VIP会员