Paper: FSA: An Efficient And Flexible C++ Toolkit For Finite State Automata Using On-Demand Computation

ACL ID P04-1065
Title FSA: An Efficient And Flexible C++ Toolkit For Finite State Automata Using On-Demand Computation
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 2004
Authors

In this paper we present the RWTH FSA toolkit – an efficient implementation of algorithms for creating and manipulating weighted finite-state automata. The toolkit has been designed using the principle of on-demand computation and offers a large range of widely used algorithms. To prove the superior efficiency of the toolkit, we compare the implemen- tation to that of other publically available toolkits. We also show that on-demand computations help to reduce memory requirements significantly without any loss in speed. To increase its flexibility, the RWTH FSA toolkit supports high-level interfaces to the programming language Python as well as a command-line tool for interactive manipulation of FSAs. Furthermore, we show how to utilize the toolkit to rapidly build a fast and accurate sta...