Patent ID: 6952667

Claim:
A method for extracting infinite ambiguity from an input finite-state transducer (EST) having a plurality of states and a plurality of arcs, comprising the steps of: assigning to each state a set of epsilon loops and a unique diacritic representative of the set; each epsilon ioop in the set of epsilon ioops beginning and ending at a qorresponding state; said assigning step defining a first representation of the input EST and a second representation of the input EST; building a first factor by inserting into the first representation of the input FST one auxiliary state for each state with a non-empty set of epsilon loops; wherein each auxiliary state has an arc that leads from the auxiliary state to the corresponding state and emits the corresponding unique diacritic when traversed; removing from the first factor at least one epsilon loop without removing the arcs corresponding to the epsilon loop; building a second factor by inserting into the second representation of the input FST two auxiliary arcs for each state with a non-empty set of epsilon loops; wherein the two auxiliary arcs are labeled with a diacritic, and wherein a first of the auxiliary arqs leads from an initial state to its corresponding state, and a second of the auxiliary arcs leads from its corresponding state to a final state; and removing from the second factor all paths having partial epsilon loops; and mapping each diacritic in the second factor to a corresponding set of epsilon loops, the first factor does not contain any infinite ambiguity while the second factor retains the infinite ambiguity of the input FST.