如何从上下文无关文法枚举树 (arxiv.org)

本文介绍了一种简单算法，用于枚举上下文无关文法 (CFG) 生成的树。该算法使用配对函数在 CFG 推导和自然数之间形成双射，以便可以从计数中唯一地解码树。这提供了一种对自然逻辑语言中的表达式进行编号的通用方法，并且有可能扩展到其他组合问题。该算法还可以推广到更通用的推导形式，包括树上的 Lempel-Ziv 编码的类似物。