Method and apparatus for extracting infinite ambiguity when factoring finite state transducers

摘要

A method extracts all infinite ambiguity from an input finite-state transducer (FST). The input FST is factorized into a first factor and a second factor such that the first factor is finitely ambiguous, and the second factor retains all infinite ambiguity of the original FST. The first factor is defined so that it replaces every loop where the input symbol of every arc is an ε (i.e., epsilon, empty string) by a single arc with ε on the input side and a diacritic on the output side. The second factor is defined so that it maps every diacritic to one or more ε-loops.