Publication Search Form

Keywords

Authors

Year

We found publication with these paramters.

Factorization of Ambiguous Finite-State Transducers

Andre Kempe
This article describes an algorithm for factorizing an ambiguous finite-state transducer (FST) into two FSTs, T1 and T2, such that T1 is functional and T2 retains the ambiguity of the original FST. The application of T2 to the output of T1 never leads to a state that does not provide a transition for the next input symbol, and always terminates in a final state. In other words, T2 contains no 'failing paths' whereas T1 in general does. Since T1 is functional, it can be factorized into a left-sequential and a right-sequential FST that jointly constitute a bimachine. The described factorization can accelerate the processing because no failing paths are ever followed.
S. Yu, A. Paun, eds., Proc. CIAA 2000, London, Ontario, Canada. Vol. 2088 of Lecture Notes in Computer Science, pp. 170-181, Springer-Verlag.
2000
2000/020

Attachments

kempe00a.pdf (53.50 kB)

kempe00a.ps.gz (43.30 kB)