Finitely subsequential transducers

Cyril Allauzen, Mehryar Mohri

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)983-994
Number of pages12
JournalInternational Journal of Foundations of Computer Science
Issue number6
StatePublished - 2003

ASJC Scopus subject areas

  • Computer Science (miscellaneous)


Dive into the research topics of 'Finitely subsequential transducers'. Together they form a unique fingerprint.

Cite this