** Next:** Determinization of Transducers
** Up:** Operations on transducers
** Previous:** Identity

The composition of two binary relations is
. The composition
operation is perhaps the most important operation on transducers. Its
implementation is similar to the intersection operation for
recognizers. In
the classical case, a transducer for the composition of two given
transducers *M*_{1} and *M*_{2} is constructed by considering the cross
product of states of *M*_{1} and *M*_{2}. A transition
exists iff there is some
such that the corresponding
transition
exists in *M*_{1} and
exists in *M*_{2}. In the case of pfst a similar construction can be
used, but instead of requiring that the output part of a transition in
*M*_{1} is identical to the input part of a transition in *M*_{2}, we now
merely require that the conjunction of both predicates is
satisfiable. In the case of identities, some further complications
arise. The effect of combining two transitions is defined by means of
the function * ct* that takes two transitions and returns a new transition:

Note that this function is not defined in case either the input part
of the second transition or the output part of the first transition is
. These cases are treated separately in the definition
below. Given two pfst
and
, the relation
is defined by
where

** Next:** Determinization of Transducers
** Up:** Operations on transducers
** Previous:** Identity
*Noord G.J.M. van*

*2001-06-22*