Patent ID: 8527273

Claim:
A method for finding N-best distinct hypotheses of an input automaton, the method comprising: computing, via a speech recognition system, an input potential for each state of a plurality of states of the input automaton to a set of final states, wherein the input potential of each state is used to determine a determinized potential of the state in a result of determinization of the input automaton and wherein the determinized potential of a particular state in the result of determinization is determined without fully determinizing the input automaton; removing redundant paths; and identifying N-best distinct paths in the result of determinization of the input automaton using the determinized potential of each of the states in the result of determinization, wherein the N-best distinct paths in the result of determinization comprise more than one best path and are labeled with the N-best hypotheses of the input automaton, wherein the identifying the N-best distinct paths comprises: adding an initial state to the result of determinization of the input automaton; creating an initialized first queue pair comprising the initial state and an initial cost element; placing the first queue pair in a queue; creating a plurality of new states from the first queue pair; applying a shortest path algorithm to each of the new states to calculate a shortest path of each of the new states; creating new queue pairs using the new states and cost elements of each new queue pair calculated via the shortest path algorithm; adding the new queue pairs to the queue; prioritizing the queue based upon a cost element of each queue pair relative to each other queue pair in the queue, wherein a queue pair in the queue with a lower cost element is given a higher priority than another queue pair in the queue with a higher cost element; selecting a queue pair from the queue with a highest priority; incrementing a pair counter; and determining whether a value of the pair counter is equal to a desired number of best paths.