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 ...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 τ is a lowest parse tree for its yield, then O（n） =O（｜｜τ｜｜ ＋ 1）, where ｜｜τ｜｜ is the length of the sentence （yield） generated by τ. The sentence can be obtained as a by-product of the parse tree. To compute sentence from its parse tree （needn＇t be lowest one）, the time complexity is O（node）＋O（｜｜τ｜｜ ＋ 1）, where node is the number of non-leaf nodes of parse tree τ. To generate both a complete lowest parse tree and its yield at the same time, the time complexity is O（｜｜τ｜｜ ＋ 1）.展开更多
Generally speaking, it is impossible for a wire-frame to define a 3D object uniquely. But wire-frame as a graphics medium is still applied in some industrial areas. A sufficient condition is presented in this paper. I...Generally speaking, it is impossible for a wire-frame to define a 3D object uniquely. But wire-frame as a graphics medium is still applied in some industrial areas. A sufficient condition is presented in this paper. If this condition is satisfied by a wire-frame, then the wire-frame can represent a 3D object uniquely The result is applied to manufacturing of progressive stripe.展开更多
基金Supported by the National Natural Science Foundation of China (Grant Nos. 60273023, 60721061)
文摘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 τ is a lowest parse tree for its yield, then O（n） =O（｜｜τ｜｜ ＋ 1）, where ｜｜τ｜｜ is the length of the sentence （yield） generated by τ. The sentence can be obtained as a by-product of the parse tree. To compute sentence from its parse tree （needn＇t be lowest one）, the time complexity is O（node）＋O（｜｜τ｜｜ ＋ 1）, where node is the number of non-leaf nodes of parse tree τ. To generate both a complete lowest parse tree and its yield at the same time, the time complexity is O（｜｜τ｜｜ ＋ 1）.
基金This work is supported by the National Natural Science Foundation of China (No.6612551).
文摘Generally speaking, it is impossible for a wire-frame to define a 3D object uniquely. But wire-frame as a graphics medium is still applied in some industrial areas. A sufficient condition is presented in this paper. If this condition is satisfied by a wire-frame, then the wire-frame can represent a 3D object uniquely The result is applied to manufacturing of progressive stripe.
