Parallel Intersection and Serial Composition of Finite State Transducers

Mike Reape, Henry Thompson

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationProceedings of the 12th Conference on Computational Linguistics - Volume 2
Place of PublicationStroudsburg, PA, USA
PublisherAssociation for Computational Linguistics
Number of pages5
ISBN (Print)9638431563
Publication statusPublished - 1988


Dive into the research topics of 'Parallel Intersection and Serial Composition of Finite State Transducers'. Together they form a unique fingerprint.

Cite this