A FILTER-BASED ALGORITHM FOR EFFICIENT COMPOSITION OF FINITE-STATE TRANSDUCERS
Cyril Allauzen, Michael Riley, Johan Schalkwyk · International Journal of Foundations of Computer Science · 2011
This paper describes a weighted finite-state transducer composition algorithm that generalizes the concept of the composition filter and presents various filters that process epsilon transitions, look-ahead along paths, and push forward labels along epsilon paths. These filters, either individually or in combination, make it possible to compose some transducers much more efficiently in time and space than otherwise possible. We present examples of this drawn, in part, from demanding speech-processing applications. The generalized composition algorithm and many of these filters have been included in Open-Fst, an open-source weighted transducer library.