AT&T Labs Research  FSM Library
Overview
The AT&T FSM library^{TM} is a set of generalpurpose software tools
available for Unix, for building, combining, optimizing, and searching
weighted finitestate acceptors and transducers. Finitestate
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 library^{TM} was to provide algorithms and
representations for phonetic, lexical, and languagemodeling
components of largevocabulary 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 largevocabulary 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.
System Components
 AT&T FSM library^{TM}: includes about 30 standalone commands to construct,
combine, determinize, minimize, and search weighted finitestate machines
(FSMs). These commands manipulate FSMs by reading from and writing
to files or pipelines.
 Dot and Dotty: programs used by the FSM library to visualize
graph representations of FSMs (Graphviz).
