Incremental composition of static decoding graphs with label pushing

Abstract

We present new results achieved in the application of incremental graph composition algorithm, in particular using the label pushing method to further reduce the final graph size. In our previous work we have shown that the incremental composition is an efficient alternative to the conventional finite state transducer (FST) determinization-composition-minimization approach, with some limitations. One of the limitations was that the word labels must stay aligned with the actual word ends. We describe an updated version of the algorithm which allows us to push the word labels relatively to the word ends to increase the effect of the minimization. The size of resulting graph is now very close to the ones produced by the conventional FST approach with label pushing. © 2010 ISCA.