Patent ID: 7240004

Claim:
A method for determining if a first weighted finite-state transducer is determinizable, comprising: receiving the first weighted finite-state transducer having at least one weight assigned to a transition between two states; determining an inverse weighted finite-state transducer from the first weighted finite-state transducer; composing the first weighted finite-state transducer and the inverse weighted finite-state transducer to form a composed weighted finite-state transducer; and determining if the composed weighted finite-state transducer meets a cycle-identity condition; wherein, if the composed weighted finite-state transducer does not meet the cycle-identity condition, the first weighted finite-state transducer is not determinizable; and if the composed weighted finite-state transducer meets the cycle identity condition, the first weighted finite-state transducer is determinizable, and creating an output indicating that the first weighted finite-state transducer meets the cycle-identity condition.