  Weighted finite-state automata (WSFAs) are commonly used in NLP. Failure
transitions are a useful extension for compactly representing backoffs or
interpolation in $n$-gram models and CRFs, which are special cases of WFSAs.
The pathsum in ordinary acyclic WFSAs is efficiently computed by the backward
algorithm in time $O(|E|)$, where $E$ is the set of transitions. However, this
does not allow failure transitions, and preprocessing the WFSA to eliminate
failure transitions could greatly increase $|E|$. We extend the backward
algorithm to handle failure transitions directly. Our approach is efficient
when the average state has outgoing arcs for only a small fraction $s \ll 1$ of
the alphabet $\Sigma$. We propose an algorithm for general acyclic WFSAs which
runs in $O{\left(|E| + s |\Sigma| |Q| T_\text{max} \log{|\Sigma|}\right)}$,
where $Q$ is the set of states and $T_\text{max}$ is the size of the largest
connected component of failure transitions. When the failure transition
topology satisfies a condition exemplified by CRFs, the $T_\text{max}$ factor
can be dropped, and when the weight semiring is a ring, the $\log{|\Sigma|}$
factor can be dropped. In the latter case (ring-weighted acyclic WFSAs), we
also give an alternative algorithm with complexity $\displaystyle O{\left(|E| +
|\Sigma| |Q| \min(1,s\pi_\text{max}) \right)}$, where $\pi_\text{max}$ is the
size of the longest failure path.
