中国科学E辑
中國科學E輯
중국과학E집
SCIENCE IN CHINA (SERIES E)
2006年
12期
1375-1413
,共39页
CFL分层构造%CFL句子计数%CFL句子词典序枚举%自然枚举%D(o)m(o)si猜想%基于文法的句子枚举%推导树枚举%无二义CFG充分必要条件%推导树文法
CFL分層構造%CFL句子計數%CFL句子詞典序枚舉%自然枚舉%D(o)m(o)si猜想%基于文法的句子枚舉%推導樹枚舉%無二義CFG充分必要條件%推導樹文法
CFL분층구조%CFL구자계수%CFL구자사전서매거%자연매거%D(o)m(o)si시상%기우문법적구자매거%추도수매거%무이의CFG충분필요조건%추도수문법
通过按推导树高度对句子分层,建立了句子集合中的分层词典序.进而发展出一种基于文法的,依分层词典序的,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句子計數和枚舉方法,穫得句子枚舉的多箇高效算法.對于無二義CFG,首先提齣一箇基礎算法N2L,時間複雜度為O(n·lg(n)),n是被枚舉句子的長度.對N2L進行改造,得到兩箇算法TD和BU,時間複雜度均為O(n).對任意CFG,利用其推導樹文法為工具後,文法無二義的限製被去除.對于一般的CFG,不論是否二義文法,也得到瞭依分層詞典序的,時間複雜度為O(n)的枚舉算法,同時枚舉齣句子及其推導樹.該文的結果,從正麵圓滿迴答瞭D(o)m(o)si提齣的未決問題,即是否有按詞典序,時間複雜度為O(n)的枚舉算法?以及是否時間複雜度僅依賴于文法結構,及被枚舉字之前同樣長度的字的箇數?本文給齣的解答甚至比原問題所期望的更好.
통과안추도수고도대구자분층,건립료구자집합중적분층사전서.진이발전출일충기우문법적,의분층사전서적,CFL구자계수화매거방법,획득구자매거적다개고효산법.대우무이의CFG,수선제출일개기출산법N2L,시간복잡도위O(n·lg(n)),n시피매거구자적장도.대N2L진행개조,득도량개산법TD화BU,시간복잡도균위O(n).대임의CFG,이용기추도수문법위공구후,문법무이의적한제피거제.대우일반적CFG,불론시부이의문법,야득도료의분층사전서적,시간복잡도위O(n)적매거산법,동시매거출구자급기추도수.해문적결과,종정면원만회답료D(o)m(o)si제출적미결문제,즉시부유안사전서,시간복잡도위O(n)적매거산법?이급시부시간복잡도부의뢰우문법결구,급피매거자지전동양장도적자적개수?본문급출적해답심지비원문제소기망적경호.
