The design principles of a weighted finite-state transducer library

We describe the algorithmic and software design principles of an object-ori ented library for weighted finite-state transducers. By taking advantage of the theory of rational power series, we were able to achieve high degrees of generality, modularity and irredundancy, while attaining competitive eff iciency in demanding speech processing applications involving weighted auto mata of more than 10(7) states and transitions. Besides its mathematical fo undation, the design also draws from important ideas in algorithm design an d programming languages: dynamic programming and shortest-paths algorithms over general semirings, object-oriented programming, lazy evaluation and me moization. (C) 2000 Published by Elsevier Science B.V. All rights reserved.