The design principles of a weighted finite-state transducer library

Mehryar Mohri, Fernando Pereira, Michael Riley

Research output: Contribution to journalArticlepeer-review

Abstract

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
Volume231
Issue number1
DOIs
StatePublished - Jan 17 2000

Keywords

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

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

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

Cite this