Efficient Transducer Composition in Vcsn

Authors

Valentin Tolmer

Type

techreport

Year

2016

Number

1514

Abstract

Transducers are used in many contexts, such as speech recognition or in order to measure the similarity between proteins. One of the core algorithms to manipulate them is the composition. This work presents the basic composition algorithm, then its extension to transducers with spontaneous transitions. A lazy adaptation of the algorithm is then proposed for both the composition and the necessary pre-processing (insplitting). Naïve variadic composition is shown to be useless in reducing the amount of computations. Finally, some benchmarks show how the implementation of the composition in Vcsn compares with OpenFST.