linear algorithm for lexicographic enumeration of cfg parse trees
文献类型：期刊论文
| 作者 | Dong YunMei |
| 刊名 | SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES
 |
| 出版日期 | 2009 |
| 卷号 | 52期号:7页码:1177-1202 |
| 关键词 | hierarchical construction of set of parse trees lexicographic enumeration of parse trees counting of parse trees |
| ISSN号 | 1009-2757 |
| 学科主题 | Computer Science ; Information Systems |
| 收录类别 | SCI |
| 公开日期 | 2011-03-18 |
| 附注 | We study CFG parse tree enumeration in this paper. By dividing the set of all parse trees into infinite hierarchies according to height of parse tree, the hierarchical lexicographic order on the set of parse trees is established. Then grammar-based algorithms for counting and enumerating CFG parse trees in this order are presented. To generate a parse tree of height n, the time complexity is O(n). If tau is a lowest parse tree for its yield, then O(n) =O(ayen gt ayen+ 1), where ayen tau ayen is the length of the sentence (yield) generated by tau. The sentence can be obtained as a by-product of the parse tree. To compute sentence from its parse tree (neednt be lowest one), the time complexity is O(node)+O(ayen tau ayen + 1), where node is the number of non-leaf nodes of parse tree tau. To generate both a complete lowest parse tree and its yield at the same time, the time complexity is O(ayen tau ayen + 1). |
| 源URL | [http://124.16.136.157/handle/311060/7960]  |
| 专题 | 软件研究所_计算机科学国家重点实验室 _期刊论文 |
| 推荐引用方式 GB/T 7714 | Dong YunMei. linear algorithm for lexicographic enumeration of cfg parse trees[J]. SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES,2009,52(7):1177-1202. |
| APA | Dong YunMei.(2009).linear algorithm for lexicographic enumeration of cfg parse trees.SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES,52(7),1177-1202. |
| MLA | Dong YunMei."linear algorithm for lexicographic enumeration of cfg parse trees".SCIENCE IN CHINA SERIES F-INFORMATION SCIENCES 52.7(2009):1177-1202. |
入库方式： OAI收割
来源：软件研究所
浏览0
下载0
收藏0
其他版本
除非特别说明，本系统中所有内容都受版权保护，并保留所有权利。