linear algorithm for lexicographic enumeration of cfg parse trees

	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.