Patent ID: 7107205

Claim:
A computer-implemented method for finite-state language processing that aligns ambiguity in an input finite-state transducer (FST) having an input side to provide a sequential FST, comprising the steps of: receiving an input string at the FST; concatenating a boundary symbol on a right side of the input FST; creating a left-deterministic input finite-state automaton (FSA) having a plurality of arcs by producing a minimal FST from the input FST and by extracting the input side and determinizing the input side from left to right, including, for every state q i with a non-empty set E E i , creating two auxiliary arcs, both labeled with the diacritic ξ i , setting one of the two auxiliary arcs for each state q i to lead from an initial state of the FST to each state q i , setting the other of the two auxiliary arcs for each state q i to lead from each state q i to an only final state of the FST, composing a factor Ξ 2 ′ to remove all partial ε loops using an equation Ξ 2 ″ = ( ⋃ i ⁢ ( ξ i ⁢ ξ i ) ) ∘ Ξ 2 ′ , composing a factor Ξ 2 ″ to replace in any sequence of two identical diacritics Ξ i Ξ i , a first diacritic Ξ i on an output side with ε and a second discritic ξ i on the input and output sides with {circumflex over (ε)} preserving a set E i of ε loops in between using an equation Ξ 2 ′″=(?{circumflex over (ε)}:?)oΞ 2 ″o(?:ε?*?:{circumflex over (ε)}), composing a factor Ξ 2 ′″ to map every remaining diacritic ξ i to a corresponding set E i of s loops using the equation Ξ 2 = ( Σ 1 out ∘ ( Ξ 2 ′ ′ ′ ⋃ ⫬ ⋃ i ⁢ ξ i ) ) * , and minimizing a resulting factor; copying at least one state of the minimal FST as many times as it occurs in different state sets of the input FST to create an aligned FST; identifying each arc in the left-deterministic FSA, and for each such arc: identifying at least one corresponding sub-path in the input EST; recording at least one alternative sub-path of the minimal FST; and aligning the sub-path with at least one other corresponding sub-path by prepending arcs with symbols representative of an empty string; replacing the boundary symbol with a symbol representing an empty string to provide an aligned sequential FST; and performing language processing using an output string of the aligned sequential FST.