CFL句子计数和分层词典序枚举

摘要：

通过按推导树高度对句子分层,建立了句子集合中的分层词典序.进而发展出一种基于文法的,依分层词典序的,CFL句子计数和枚举方法,获得句子枚举的多个高效算法.对于无二义CFG,首先提出一个基础算法N2L,时间复杂度为O(n·lg(n)),n是被枚举句子的长度.对N2L进行改造,得到两个算法TD和BU,时间复杂度均为O(n).对任意CFG,利用其推导树文法为工具后,文法无二义的限制被去除.对于一般的CFG,不论是否二义文法,也得到了依分层词典序的,时间复杂度为O(n)的枚举算法,同时枚举出句子及其推导树.该文的结果,从正面圆满回答了D(o)m(o)si提出的未决问题,即是否有按词典序,时间复杂度为O(n)的枚举算法?以及是否时间复杂度仅依赖于文法结构,及被枚举字之前同样长度的字的个数?本文给出的解答甚至比原问题所期望的更好.

关键词：CFL分层构造、CFL句子计数、CFL句子词典序枚举、自然枚举、D(o)m(o)si猜想、基于文法的句子枚举、推导树枚举、无二义CFG充分必要条件、推导树文法

所属期刊栏目：36

分类号：TP3(计算技术、计算机技术)

资助基金：国家自然科学基金60273023;69873042

在线出版日期：2007-03-28（万方平台首次上网日期，不代表论文的发表时间）

页数：共39页

页码：1375-1413