Patent ID: 7266491

Claim:
A method of generating a sentence from a semantic representation, the method comprising: (A) mapping the semantic representation to an unordered set of syntactic nodes; (B) using grammar rules from a generation grammar and statistical goodness measure values from a corresponding analysis grammar to create a tree structure to order the syntactic nodes, comprising: (B)(1) selecting a syntactic node to be the root node of a new syntactic tree: (B)(2) identifying generation grammar rules that apply to each leaf node in the tree, by testing rule conditions on semantically-derived attributes of the nodes; (B)(3) generating syntactic substructures described by each applicable rule and determining a statistical goodness measure value for each substructure; and (B)(4) selecting the substructure with the highest statistical goodness measure value to use to expand the tree, comprising: (B)(4)(i) discarding generated substructures that have lower statistical goodness measure values than substructures generated by alternative equivalent generation grammar rules at other phrase levels; (B)(4)(ii) adding the remaining substructure at the current phrase level with the highest statistical goodness measure value to the current syntactic tree; and (B)(4)(iii) if no substructures exist at the current phrase level, step down one phrase level and repeat method steps (B)(4)(i) and (B)(4)(ii); and (C) generating the sentence from the tree structure.