Paper: Parallel Intersection And Serial Composition Of Finite State Transducers

ACL ID C88-2113
Title Parallel Intersection And Serial Composition Of Finite State Transducers
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1988
Authors

We describe a linguistically expressive and easy to implement parallel semantics for quasi-deterministic finite state transducers (FSTS) used as acceptors. Algorithms are given for detemain- ing acceptance of pairs of phoneme strings given a parallel suite of such transducers and for constructing the equivalent single transducer by parallel intersection. An algorithm for constructing the serial composition of a sequence of such trans- ducers is also given. This algorithm can produce generally non- detemlinislic FSTS and an algorithm is presented for eliminat- ing the unacceptable nondeterminism. Finally, the work is dis- cussed in the context of other work on finite state transducers.