Operations on finite state transducers

Which FSA operations still work for FSTs, and which new operations do two-tape paths make possible? Union, concatenation, and Kleene closure combine paths much as they do for FSAs. Projection, inversion, and composition instead use the fact that every path has two labels.

The regular operations

Suppose that $T_1$ and $T_2$ describe relations $R_1 \subseteq \Sigma_1^* \times \Gamma_1^*$ and $R_2 \subseteq \Sigma_2^* \times \Gamma_2^*$.

The union $T_1 \cup T_2$ describes $R_1 \cup R_2$. As with FSAs, we relabel the states to make the two state sets disjoint, add a new initial state, and connect it to the two old initial states with $\epsilon:\epsilon$ transitions.

The concatenation $T_1T_2$ describes the relation

\[ R_1R_2 = \{\langle x_1x_2,y_1y_2\rangle \mid \langle x_1,y_1\rangle \in R_1 \land \langle x_2,y_2\rangle \in R_2\}. \]

We construct it by connecting each final state of $T_1$ to the initial state of $T_2$ with an $\epsilon:\epsilon$ transition. The Kleene closure $T^*$ then describes any finite concatenation of pairs from $\mathbb{R}(T)$, including $\langle\epsilon,\epsilon\rangle$.

Thus, the rational relations are closed under union, concatenation, and Kleene closure. This is why the class is called rational: it is obtained by applying the regular operations to finite sets of string pairs (Kaplan and Kay 1994).

Projection and inversion

The input projection $\pi_1(T)$ removes the output labels from $T$; the output projection $\pi_2(T)$ removes the input labels. Each projection is an FSA.

\[ \begin{aligned} \mathbb{L}(\pi_1(T)) &= \{x \mid \exists y\;\langle x,y\rangle \in \mathbb{R}(T)\} \\ \mathbb{L}(\pi_2(T)) &= \{y \mid \exists x\;\langle x,y\rangle \in \mathbb{R}(T)\} \end{aligned} \]

Both languages are thus regular. Projection gives us a useful test: if a proposed transduction has a nonregular input or output projection, no FST can describe it (Kaplan and Kay 1994).

The projection claim follows directly from paths. Take any accepting path in $T$. Erasing the output label on each transition leaves a path through the same states whose label is the path’s input string. Thus, every input paired by $T$ is accepted by $\pi_1(T)$. Conversely, every accepting path in $\pi_1(T)$ came from a path in $T$; restoring its output labels supplies some paired output string. These two directions prove the first equality above. The proof for $\pi_2(T)$ is identical with the tapes reversed.

The inverse $T^{-1}$ swaps the labels on every transition.

\[ \mathbb{R}(T^{-1}) = \{\langle y,x\rangle \mid \langle x,y\rangle \in \mathbb{R}(T)\} \]

If $T$ maps underlying forms to surface forms, $T^{-1}$ relates those surface forms to their possible underlying analyses. Inversion preserves rationality, though the inverse of a functional transducer need not be functional (Kaplan and Kay 1994).

Here too the proof is path by path. A path labeled $x:y$ in $T$ has the same sequence of states and is labeled $y:x$ after every transition label is swapped. Swapping twice restores the original path, so the correspondence works in both directions.

Composition

Concatenation places two input-output pairs next to one another. Composition instead feeds the output of one relation into the input of another. If

\[ R_1 \subseteq \Sigma^* \times \Gamma^* \qquad\text{and}\qquad R_2 \subseteq \Gamma^* \times \Delta^*, \]

then

\[ R_2 \circ R_1 = \{\langle x,z\rangle \mid \exists y\;[\langle x,y\rangle \in R_1 \land \langle y,z\rangle \in R_2]\}. \]

The notation follows ordinary function composition: $R_1$ applies first and $R_2$ applies second. A transducer for $R_2 \circ R_1$ has product states $Q_1 \times Q_2$. Its transitions pair a transition in $T_1$ with a transition in $T_2$ whenever the output label of the first matches the input label of the second (Kaplan and Kay 1994; Mohri et al. 2002).

Why does the product construction work? First suppose there are no epsilon labels. The product-state invariant is:

After reaching $(q_1,q_2)$, the first transducer has read some $x$ and produced some $y$, while the second has read that same $y$ and produced some $z$.

The initial pair satisfies the invariant with three empty strings. A product transition may advance only when the intermediate labels match, so it extends both copies of $y$ by the same symbol. It also appends the first transition’s input to $x$ and the second transition’s output to $z$. Thus, every transition preserves the invariant.

If the product reaches a pair of final states, it has found paths $x:y$ in $T_1$ and $y:z$ in $T_2$, so $\langle x,z\rangle\in R_2\circ R_1$. This proves soundness. Conversely, suppose such paths exist. Pair their first transitions, then their second transitions, and so on. Their intermediate strings are identical, so every required product transition exists, and the product accepts $x:z$. This proves completeness for the epsilon-free case.

Epsilon labels make this construction less direct. One transducer may need to advance while the other remains in place, and an implementation must avoid generating the same composed path by arbitrarily many interleavings of epsilon transitions. Epsilon transitions thus require special handling (Mohri et al. 2002). Standard composition algorithms handle the interleavings with an epsilon filter (Gorman and Sproat 2021).

Question

Let $T_1$ map /kæt+z/ to /kætz/, and let $T_2$ map /tz/ to [ts]. Which composition maps /kæt+z/ to [kæts]?

Answer

$T_2 \circ T_1$. The intermediate string /kætz/ is the output of $T_1$ and the input of $T_2$.

Operations that do not preserve rationality

Rational relations are not closed under intersection or complement. This is an important difference between FSTs and FSAs (Kaplan and Kay 1994).

We prove the intersection result with two concrete relations:

\[ \begin{aligned} R_1 &= \{\langle a^n,b^nc^m\rangle\mid n,m\geq0\},\\ R_2 &= \{\langle a^n,b^mc^n\rangle\mid n,m\geq0\}. \end{aligned} \]

Both are rational. A transducer for $R_1$ loops on $a:b$ and then on $\epsilon:c$. A transducer for $R_2$ first loops on $\epsilon:b$ and then on $a:c$.

Now fix a pair in their intersection. Its input must be $a^n$ in both relations. In $R_1$, this forces exactly $n$ copies of $b$ in the output. In $R_2$, it forces exactly $n$ copies of $c$. Thus,

\[ R_1\cap R_2=\{\langle a^n,b^nc^n\rangle\mid n\geq0\}. \]

The output projection is $\{b^nc^n\mid n\geq0\}$, which is nonregular by the pumping-lemma argument from the preceding section. If the intersection were rational, that projection would have to be regular. We have reached a contradiction, so rational relations are not closed under intersection.

The complement result now follows from this one. Suppose rational relations were closed under complement relative to the universal relation over the fixed input and output alphabets. They are already closed under union. De Morgan’s law would then give

\[ R_1\cap R_2=\overline{\overline{R_1}\cup\overline{R_2}}, \]

making them closed under intersection. The explicit counterexample shows that this consequence is false. Thus, complement cannot be a general FST operation either.

These nonclosure results apply to arbitrary rational relations. Tighter subclasses must be considered separately. For instance, $p$-subsequential transductions are closed under composition and union (Mohri 1997). We will keep the general case separate from such special cases.

References

Gorman, Kyle, and Richard Sproat. 2021. Finite-State Text Processing. Synthesis Lectures on Human Language Technologies. Springer International Publishing. https://doi.org/10.1007/978-3-031-02179-4.

Kaplan, Ronald M., and Martin Kay. 1994. “Regular Models of Phonological Rule Systems.” Computational Linguistics 20 (3): 331–78. https://aclanthology.org/J94-3001/.

Mohri, Mehryar. 1997. “Finite-State Transducers in Language and Speech Processing.” Computational Linguistics 23 (2): 269–311. https://aclanthology.org/J97-2003/.

Mohri, Mehryar, Fernando Pereira, and Michael Riley. 2002. “Weighted Finite-State Transducers in Speech Recognition.” Computer Speech & Language 16 (1): 69–88. https://doi.org/10.1006/csla.2001.0184.

--- title: Operations on finite state transducers bibliography: ../../references.bib --- Which FSA operations still work for FSTs, and which new operations do two-tape paths make possible? Union, concatenation, and Kleene closure combine paths much as they do for FSAs. Projection, inversion, and composition instead use the fact that every path has two labels. ## The regular operations Suppose that $T_1$ and $T_2$ describe relations $R_1 \subseteq \Sigma_1^* \times \Gamma_1^*$ and $R_2 \subseteq \Sigma_2^* \times \Gamma_2^*$. The **union** $T_1 \cup T_2$ describes $R_1 \cup R_2$. As with FSAs, we relabel the states to make the two state sets disjoint, add a new initial state, and connect it to the two old initial states with $\epsilon:\epsilon$ transitions. The **concatenation** $T_1T_2$ describes the relation $$ R_1R_2 = \{\langle x_1x_2,y_1y_2\rangle \mid \langle x_1,y_1\rangle \in R_1 \land \langle x_2,y_2\rangle \in R_2\}. $$ We construct it by connecting each final state of $T_1$ to the initial state of $T_2$ with an $\epsilon:\epsilon$ transition. The **Kleene closure** $T^*$ then describes any finite concatenation of pairs from $\mathbb{R}(T)$, including $\langle\epsilon,\epsilon\rangle$. Thus, the rational relations are closed under union, concatenation, and Kleene closure. This is why the class is called *rational*: it is obtained by applying the regular operations to finite sets of string pairs [@kaplan1994regular]. ## Projection and inversion The **input projection** $\pi_1(T)$ removes the output labels from $T$; the **output projection** $\pi_2(T)$ removes the input labels. Each projection is an FSA. $$ \begin{aligned} \mathbb{L}(\pi_1(T)) &= \{x \mid \exists y\;\langle x,y\rangle \in \mathbb{R}(T)\} \\ \mathbb{L}(\pi_2(T)) &= \{y \mid \exists x\;\langle x,y\rangle \in \mathbb{R}(T)\} \end{aligned} $$ Both languages are thus regular. Projection gives us a useful test: if a proposed transduction has a nonregular input or output projection, no FST can describe it [@kaplan1994regular]. The projection claim follows directly from paths. Take any accepting path in $T$. Erasing the output label on each transition leaves a path through the same states whose label is the path's input string. Thus, every input paired by $T$ is accepted by $\pi_1(T)$. Conversely, every accepting path in $\pi_1(T)$ came from a path in $T$; restoring its output labels supplies some paired output string. These two directions prove the first equality above. The proof for $\pi_2(T)$ is identical with the tapes reversed. The **inverse** $T^{-1}$ swaps the labels on every transition. $$ \mathbb{R}(T^{-1}) = \{\langle y,x\rangle \mid \langle x,y\rangle \in \mathbb{R}(T)\} $$ If $T$ maps underlying forms to surface forms, $T^{-1}$ relates those surface forms to their possible underlying analyses. Inversion preserves rationality, though the inverse of a functional transducer need not be functional [@kaplan1994regular]. Here too the proof is path by path. A path labeled $x:y$ in $T$ has the same sequence of states and is labeled $y:x$ after every transition label is swapped. Swapping twice restores the original path, so the correspondence works in both directions. ## Composition Concatenation places two input-output pairs next to one another. **Composition** instead feeds the output of one relation into the input of another. If $$ R_1 \subseteq \Sigma^* \times \Gamma^* \qquad\text{and}\qquad R_2 \subseteq \Gamma^* \times \Delta^*, $$ then $$ R_2 \circ R_1 = \{\langle x,z\rangle \mid \exists y\;[\langle x,y\rangle \in R_1 \land \langle y,z\rangle \in R_2]\}. $$ The notation follows ordinary function composition: $R_1$ applies first and $R_2$ applies second. A transducer for $R_2 \circ R_1$ has product states $Q_1 \times Q_2$. Its transitions pair a transition in $T_1$ with a transition in $T_2$ whenever the output label of the first matches the input label of the second [@kaplan1994regular; @mohri_weighted_2002]. Why does the product construction work? First suppose there are no epsilon labels. The **product-state invariant** is: > After reaching $(q_1,q_2)$, the first transducer has read some $x$ and produced some $y$, while the second has read that same $y$ and produced some $z$. The initial pair satisfies the invariant with three empty strings. A product transition may advance only when the intermediate labels match, so it extends both copies of $y$ by the same symbol. It also appends the first transition's input to $x$ and the second transition's output to $z$. Thus, every transition preserves the invariant. If the product reaches a pair of final states, it has found paths $x:y$ in $T_1$ and $y:z$ in $T_2$, so $\langle x,z\rangle\in R_2\circ R_1$. This proves soundness. Conversely, suppose such paths exist. Pair their first transitions, then their second transitions, and so on. Their intermediate strings are identical, so every required product transition exists, and the product accepts $x:z$. This proves completeness for the epsilon-free case. Epsilon labels make this construction less direct. One transducer may need to advance while the other remains in place, and an implementation must avoid generating the same composed path by arbitrarily many interleavings of epsilon transitions. Epsilon transitions thus require special handling [@mohri_weighted_2002]. Standard composition algorithms handle the interleavings with an epsilon filter [@gorman_finite-state_2021]. ::: {.callout-caution} ## Question Let $T_1$ map /kæt+z/ to /kætz/, and let $T_2$ map /tz/ to [ts]. Which composition maps /kæt+z/ to [kæts]? ::: ::: {.callout-tip collapse=true} ## Answer $T_2 \circ T_1$. The intermediate string /kætz/ is the output of $T_1$ and the input of $T_2$. ::: ## Operations that do not preserve rationality Rational relations are not closed under intersection or complement. This is an important difference between FSTs and FSAs [@kaplan1994regular]. We prove the intersection result with two concrete relations: $$ \begin{aligned} R_1 &= \{\langle a^n,b^nc^m\rangle\mid n,m\geq0\},\\ R_2 &= \{\langle a^n,b^mc^n\rangle\mid n,m\geq0\}. \end{aligned} $$ Both are rational. A transducer for $R_1$ loops on $a:b$ and then on $\epsilon:c$. A transducer for $R_2$ first loops on $\epsilon:b$ and then on $a:c$. Now fix a pair in their intersection. Its input must be $a^n$ in both relations. In $R_1$, this forces exactly $n$ copies of $b$ in the output. In $R_2$, it forces exactly $n$ copies of $c$. Thus, $$ R_1\cap R_2=\{\langle a^n,b^nc^n\rangle\mid n\geq0\}. $$ The output projection is $\{b^nc^n\mid n\geq0\}$, which is nonregular by the pumping-lemma argument from the preceding section. If the intersection were rational, that projection would have to be regular. We have reached a contradiction, so rational relations are not closed under intersection. The complement result now follows from this one. Suppose rational relations were closed under complement relative to the universal relation over the fixed input and output alphabets. They are already closed under union. De Morgan's law would then give $$ R_1\cap R_2=\overline{\overline{R_1}\cup\overline{R_2}}, $$ making them closed under intersection. The explicit counterexample shows that this consequence is false. Thus, complement cannot be a general FST operation either. These nonclosure results apply to arbitrary rational relations. Tighter subclasses must be considered separately. For instance, $p$-subsequential transductions are closed under composition and union [@mohri_fst_1997]. We will keep the general case separate from such special cases.