Patent ID: 6243679
Filing Date: 2001-06-05
Classification: G10L

Abstract:
A method for determinizing a weighted and labeled non-deterministic graph using a data processing system, the non-deterministic graph stored in a memory of the data processing device, the method comprising:receiving speech signals;converting the speech signals into word sequences, the word sequences comprising words;evaluating a probability that each word of each word sequence would be spoken;interpreting the word sequences based on the non-deterministic graph, the non-deterministic graph having nodes and arcs connecting the nodes, the arcs labeled with the words and weights corresponding to the probabilities; anddeterminizing the non-deterministic graph to create a determinized graph having nodes and arcs connecting the nodes, the nodes having substates, each substate corresponding to a node of the non-deterministic graph and containing a remainder, each arc labeled with a minimum weight.