I present a simple algorithm for enumerating the trees generated by a Context Free Grammar (CFG). The algorithm uses a pairing function to form a bijection between CFG derivations and natural numbers, so that trees can be uniquely decoded from counting. This provides a general way to number expressions in natural logical languages, and potentially can be extended to other combinatorial problems. I also show how this algorithm may be generalized to more general forms of derivation, including analogs of Lempel-Ziv coding on trees.


翻译:我提出了一种简单的算法,用于枚举由上下文无关语法(CFG)生成的树。该算法使用配对函数将CFG派生和自然数形成双射,使得可以通过计数唯一地解码树。这提供了一种以自然逻辑语言中表达式编号的一般方法,并且可能可以扩展到其他组合问题。我还展示了如何将此算法推广到更一般的推导形式,包括树上的Lempel-Ziv编码模拟。

0
下载
关闭预览

相关内容

自然语言处理顶会NAACL2022最佳论文出炉!
专知会员服务
42+阅读 · 2022年6月30日
专知会员服务
127+阅读 · 2021年6月18日
专知会员服务
76+阅读 · 2021年3月16日
Linux导论,Introduction to Linux,96页ppt
专知会员服务
77+阅读 · 2020年7月26日
强化学习最新教程,17页pdf
专知会员服务
174+阅读 · 2019年10月11日
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
ERNIE Tutorial(论文笔记 + 实践指南)
AINLP
30+阅读 · 2019年8月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
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-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
自然语言处理 (三) 之 word embedding
DeepLearning中文论坛
19+阅读 · 2015年8月3日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Arxiv
0+阅读 · 2023年6月15日
Arxiv
12+阅读 · 2022年4月30日
Learning Implicit Fields for Generative Shape Modeling
Arxiv
10+阅读 · 2018年12月6日
Arxiv
23+阅读 · 2017年3月9日
VIP会员
相关资讯
GNN 新基准!Long Range Graph Benchmark
图与推荐
0+阅读 · 2022年10月18日
ERNIE Tutorial(论文笔记 + 实践指南)
AINLP
30+阅读 · 2019年8月28日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
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-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
【推荐】自然语言处理(NLP)指南
机器学习研究会
35+阅读 · 2017年11月17日
自然语言处理 (NLP)资源大全
机械鸡
35+阅读 · 2017年9月17日
自然语言处理 (三) 之 word embedding
DeepLearning中文论坛
19+阅读 · 2015年8月3日
相关基金
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
Top
微信扫码咨询专知VIP会员