## Abstract

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

Original language | English (US) |
---|---|

Pages (from-to) | 24-34 |

Number of pages | 11 |

Journal | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |

Volume | 2608 |

DOIs | |

State | Published - 2003 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)