TY - JOUR
T1 - The design principles of a weighted finite-state transducer library
AU - Mohri, Mehryar
AU - Pereira, Fernando
AU - Riley, Michael
N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
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 -