**Gertjan van Noord and Dale Gerdemann**

An extension to finite state transducers is presented, in which
atomic symbols are replaced by arbitrary predicates over symbols.
The extension is motivated by applications in natural language
processing (but may be more widely applicable) as well as by the
observation that transducers with predicates generally have fewer
states and fewer transitions.

Although the extension is fairly trivial for finite state acceptors, the introduction of predicates is more interesting for transducers. It is shown how various operations on transducers (e.g. composition) can be implemented, as well as how the transducer determinization algorithm can be generalized for predicate-augmented finite state transducers.

- Introduction
- Finite State Recognizers with Predicates
- Transducers with Predicates and Identities
- Practical Considerations
- Future Work
- Bibliography
- About this document ...