The Algorithm Design Manual
About the Book
Programming Challenges

The Stony Brook Algorithm Repository

Steven Skiena
Stony Brook University
Dept. of Computer Science

AT&T FSM Library – Finite-State Machine Library

The AT&T FSM libraryTM is a set of general-purpose software tools available for Unix, for building, combining, optimizing, and searching weighted finite-state acceptors and transducers. Finite-state transducers are automata for which each transition has an output label in addition to the more familiar input label. Weighted acceptors or transducers are acceptors or transducers in which each transition has a weight as well as the input or input and output labels.

The original goal of the AT&T FSM libraryTM was to provide algorithms and representations for phonetic, lexical, and language-modeling components of large-vocabulary speech recognition systems. This imposed the following requirements:

* Generality: to support the representation and use of the various information sources in speech recognition * Modularity: to allow rapid experimentation with different representations * Efficiency: to support competitive large-vocabulary recognition using automata of more than 10 million states and transitions.

The mathematical foundation of the library is the theory of rational power series, which supplies the semantics for the objects and operations and creates opportunity for optimizations such as determinization and minimization.

  • Download Files (local site)
  • Offical Site

    Problem Links

    Finite State Machine Minimization (9)

    This page last modified on 2008-07-10 .