Publications
Authors:
  • Andre Kempe
Citation:
S. Yu, A. Paun, eds., Proc. CIAA 2000, London, Ontario, Canada. Vol. 2088 of Lecture Notes in Computer Science, pp. 170-181, Springer-Verlag.
Abstract:
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.
Year:
2000
Report number:
2000/020
Attachments: