Finite State Transducers with Predicates and Identities
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.
Noord G.J.M. van