The design principles of a weighted finite-state transducer library

Mehryar Mohri, Fernando Pereira, Michael Riley

Research output: Contribution to journalArticlepeer-review


We describe the algorithmic and software design principles of an object-oriented 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 efficiency in demanding speech processing applications involving weighted automata of more than 107 states and transitions. Besides its mathematical foundation, the design also draws from important ideas in algorithm design and programming languages: dynamic programming and shortest-paths algorithms over general semirings, object-oriented programming, lazy evaluation and memoization.

Original languageEnglish (US)
Pages (from-to)17-32
Number of pages16
JournalTheoretical Computer Science
Issue number1
StatePublished - Jan 17 2000


  • Finite-state transducers
  • Rational power series
  • Speech recognition
  • Weighted automata

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'The design principles of a weighted finite-state transducer library'. Together they form a unique fingerprint.

Cite this