Parallel intersection and serial composition of finite state transducers
Mike Reape, Henry S. Thompson · 1988
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 determining 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 transducers is also given. This algorithm can produce generally nondeterministic FSTS and an algorithm is presented for eliminating the unacceptable nondeterminism. Finally, the work is discussed in the context of other work on finite state transducers.