Patent ID: 6266634
Filing Date: 2001-07-24
Classification: G10L

Abstract:
A method for generating an approximate weighted finite-state automaton from a non-deterministic weighted finite-state automaton, each of the non-deterministic weighted finite-state automaton and the approximate weighted finite-state automaton usable to recognize a pattern in a pattern recognition method comprising:determinizing the non-deterministic weighted finite-state automaton to form the approximate weighted finite-state automaton on a state-by-state basis;determining, as each set of states of the non-deterministic weighted finite-state automaton reachable from a current state of the approximate weighted finite-state automaton is determinized to form at least one proposed new state of the approximate weighted finite-state automaton, for each proposed new state, if that proposed new state is sufficiently similar to a previous state of the approximate weighted finite-state automaton;creating a transition from the current state of the approximate weighted finite-state automaton to the previous state of the approximate weighted finite-state automaton if that proposed new state is sufficiently similar to the previous state;creating a transition from the current state of the approximate weighted finite-state automaton to the proposed new state of the approximate weighted finite-state automaton if that proposed new state is not sufficiently similar to any previous state of the approximate weighted finite-state automaton; andperforming recognition using the approximate weighted finite-state automaton.