TY - JOUR
T1 - Finitely subsequential transducers
AU - Allauzen, Cyril
AU - Mohri, Mehryar
PY - 2003
Y1 - 2003
N2 - Finitely subsequential transducers are efficient finite-state transducers with a finite number of final outputs and are used in a variety of applications. Not all transducers admit equivalent finitely subsequential transducers however. We briefly describe an existing generalized determinization algorithm for finitely subsequential transducers and give the first characterization of finitely subsequentiable transducers, transducers that admit equivalent finitely subsequential transducers. Our characterization shows the existence of an efficient algorithm for testing finite subsequentiability. We have fully implemented the generalized determinization algorithm and the algorithm for testing finite subsequentiability. We report experimental results showing that these algorithms are practical in large-vocabulary speech recognition applications. The theoretical formulation of our results is the equivalence of the following three properties for finite-state transducers: determinizability in the sense of the generalized algorithm, finite subsequentiability, and the twins property.
AB - Finitely subsequential transducers are efficient finite-state transducers with a finite number of final outputs and are used in a variety of applications. Not all transducers admit equivalent finitely subsequential transducers however. We briefly describe an existing generalized determinization algorithm for finitely subsequential transducers and give the first characterization of finitely subsequentiable transducers, transducers that admit equivalent finitely subsequential transducers. Our characterization shows the existence of an efficient algorithm for testing finite subsequentiability. We have fully implemented the generalized determinization algorithm and the algorithm for testing finite subsequentiability. We report experimental results showing that these algorithms are practical in large-vocabulary speech recognition applications. The theoretical formulation of our results is the equivalence of the following three properties for finite-state transducers: determinizability in the sense of the generalized algorithm, finite subsequentiability, and the twins property.
UR - http://www.scopus.com/inward/record.url?scp=9544224403&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=9544224403&partnerID=8YFLogxK
U2 - 10.1142/S0129054103002126
DO - 10.1142/S0129054103002126
M3 - Article
AN - SCOPUS:9544224403
SN - 0129-0541
VL - 14
SP - 983
EP - 994
JO - International Journal of Foundations of Computer Science
JF - International Journal of Foundations of Computer Science
IS - 6
ER -