The design principles of a weighted finite-state transducer library

Mehryar Mohri; Fernando Pereira; Michael Riley

doi:10.1016/S0304-3975(99)00014-6

The design principles of a weighted finite-state transducer library

Mehryar Mohri, Fernando Pereira, Michael Riley

Computer Science

Research output: Contribution to journal › Article › peer-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 10⁷ 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 language	English (US)
Pages (from-to)	17-32
Number of pages	16
Journal	Theoretical Computer Science
Volume	231
Issue number	1
DOIs	https://doi.org/10.1016/S0304-3975(99)00014-6
State	Published - Jan 17 2000

Keywords

Finite-state transducers
Rational power series
Speech recognition
Weighted automata

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1016/S0304-3975(99)00014-6

Cite this

@article{805b60091a8a4ea4af8aab530029a994,

title = "The design principles of a weighted finite-state transducer library",

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.",

keywords = "Finite-state transducers, Rational power series, Speech recognition, Weighted automata",

author = "Mehryar Mohri and Fernando Pereira and Michael Riley",

year = "2000",

month = jan,

day = "17",

doi = "10.1016/S0304-3975(99)00014-6",

language = "English (US)",

volume = "231",

pages = "17--32",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

number = "1",

}

TY - JOUR

T1 - The design principles of a weighted finite-state transducer library

AU - Mohri, Mehryar

AU - Pereira, Fernando

AU - Riley, Michael

PY - 2000/1/17

Y1 - 2000/1/17

N2 - 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.

AB - 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.

KW - Finite-state transducers

KW - Rational power series

KW - Speech recognition

KW - Weighted automata

UR - http://www.scopus.com/inward/record.url?scp=0012306376&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0012306376&partnerID=8YFLogxK

U2 - 10.1016/S0304-3975(99)00014-6

DO - 10.1016/S0304-3975(99)00014-6

M3 - Article

AN - SCOPUS:0012306376

VL - 231

SP - 17

EP - 32

JO - Theoretical Computer Science

JF - Theoretical Computer Science

SN - 0304-3975

IS - 1

ER -

The design principles of a weighted finite-state transducer library

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this