01962764

a

01962764 Allauzen, Cyril Mohri, Mehryar $p$-subsequentiable transducers. Champarnaud, Jean-Marc (ed.) et al., Implementation and application of automata. 7th international conference, CIAA 2002, Tours, France, July 3--5, 2002. Revised papers. Berlin: Springer (ISBN 3-540-40391-4/pbk). Lect. Notes Comput. Sci. 2608, 24-34 (2003). 2003 Berlin: Springer EN

http://link.springer.de/link/service/series/0558/bibs/2608/26080024.htm

Summary: $p$-subsequential transducers are efficient finite-state transducers with $p$ final outputs used in a variety of applications. Not all transducers admit equivalent $p$-subsequential transducers however. We briefly describe an existing generalized determinization algorithm for $p$-subsequential transducers and give the first characterization of $p$-subsequ-entiable transducers, transducers that admit equivalent $p$-subsequential transducers. Our characterization shows the existence of an efficient algorithm for testing $p$-subsequentiability. We have fully implemented the generalized determinization algorithm and the algorithm for testing $p$-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, $p$-subsequentiability, and the twins property.