This Issue


International Journal of Foundations of Computer Science: Vol. 14, No. 06
Print ISSN: 0129-0541
Online ISSN: 1793-6373

 
writing-guides   ealerts
Connect with WS
 


FINITELY SUBSEQUENTIAL TRANSDUCERS

CYRIL ALLAUZEN

AT&T Labs — Research, 180 Park Avenue, Florham Park, NJ 07932, USA

MEHRYAR MOHRI

AT&T Labs — Research, 180 Park Avenue, Florham Park, NJ 07932, USA

Received: 15 November 2002
Accepted: 14 March 2002

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.

Cited by (3):
. (2013) ON THE DISAMBIGUATION OF FINITE AUTOMATA AND FUNCTIONAL TRANSDUCERS. International Journal of Foundations of Computer Science 24:06, 847-862. Online publication date: 1-Sep-2013. [Abstract | PDF (397 KB) | PDF Plus (403 KB)]
, , . (2013) An algorithm to design finite automata that accept strings over input symbol a and b having exactly x number of a & y number of b. 2013 International Conference on Information Systems and Computer Networks, 1-4. [CrossRef]
, . (2004) An optimal pre-determinization algorithm for weighted transducers. Theoretical Computer Science 328:1-2, 3-18. Online publication date: 1-Nov-2004. [CrossRef]