Method and apparatus for generating deterministic approximate weighted finite-state automata
Systems and methods for determinization and minimization a finite state transducer for speech recognition Patent #: 6243679
ApplicationNo. 10176465 filed on 06/20/2002
US Classes:704/255, Specialized models704/1, LINGUISTICS704/256.8Discrete density, e.g., Vector Quantization preprocessor, look up tables (EPO)
ExaminersPrimary: Hudspeth, David
Assistant: Sked, Matthew J.
International ClassesG10L 15/00
AbstractFinite-state transducers and weighted finite-state automata may not be determinizable. The twins property can be used to characterize the determinizability of such devices. For a weighted finite-state automaton or transducer, that weighted finite-state automaton or transducer and its inverse are intersected or composed, respectively. The resulting device is checked to determine if it has the cycle-identity property. If not, the original weighted finite-state automaton or transducer is not determinizable. For a weighted or unweighted finite-state transducer, that device is checked to determine if it is functional. If not, that device is not determinizable. That device is then composed with its inverse. The composed device is checked to determine if every edge in the composed device having a cycle-accessible end state meets at least one of a number of conditions. If so, the original device has the twins property. If the original device has the twins property, then it is determinizable.