Composition

The composition of two binary relations is $R_1 \circ R_2 = \{ (x_1,x_3)\vert (x_1,x_2)\in R_1, (x_2,x_3)\in R_2\}$. 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₁ and M₂ is constructed by considering the cross product of states of M₁ and M₂. A transition $((p_1,p_2),\sigma_d,\sigma_r,(q_1,q_2))$ exists iff there is some $\sigma$ such that the corresponding transition $(p_1,\sigma_d,\sigma,q_1)$ exists in M₁ and $(p_2,\sigma,\sigma_r,q_2)$ exists in M₂. In the case of pfst a similar construction can be used, but instead of requiring that the output part of a transition in M₁ is identical to the input part of a transition in M₂, 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:

$$\begin{array}{ll} \mbox{ct}((p_1,\pi_1,\pi_1,q_1,1),(p_2,\pi... ... & \mbox{~~~~if~satisfiable($\pi_1\wedge\pi_2$)}\\ \end{array}$$

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 $\epsilon$. These cases are treated separately in the definition below. Given two pfst $M_1=(Q_1,\Sigma,\Pi,E_1,S_1,F_1)$ and $M_2=(Q_2,\Sigma,\Pi,E_2,S_2,F_2)$, the relation $R(M_1) \circ R(M_2)$ is defined by $M=(Q_1 \times Q_2,\Sigma,\Pi,E,S_1\times S_2, F_1\times F_2)$ where

$$E = \begin{array}[t]{ll} & \{ ct(e_1,e_2) \vert e_1\in E_1,e... ...rt p_2\in Q_2, (p_1,\phi,\epsilon,q_1,0)\in E_1 \} \end{array}$$