# Algorithms for Acyclic Weighted Finite-State Automata with Failure Arcs

arXiv: https://arxiv.org/abs/2301.06862 · HTML: https://mlsanity.com/paper/2301.06862/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 30 references that are in the map.
- First posted on arXiv 17 Jan 2023.

## Builds on (most cited first, 8 of 8)

- [Theoretical Limitations of Self-Attention in Neural Sequence Models](https://mlsanity.com/paper/1906.06755/) (2019)
- [Overcoming a Theoretical Limitation of Self-Attention](https://mlsanity.com/paper/2202.12172/) (2022)
- [Ordered Neurons: Integrating Tree Structures into Recurrent Neural Networks](https://mlsanity.com/paper/1810.09536/) (2018)
- [Neuro-Symbolic Language Modeling with Automaton-augmented Retrieval](https://mlsanity.com/paper/2201.12431/) (2022)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [Rational Recurrences](https://mlsanity.com/paper/1808.09357/) (2018)
- [Lexically Aware Semi-Supervised Learning for OCR Post-Correction](https://mlsanity.com/paper/2111.02622/) (2021)
- [SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machines](https://mlsanity.com/paper/1805.06061/) (2018)

## Built on by (most cited first, 1 of 1)

- [Unifying Global and Near-Context Biasing in a Single Trie Pass](https://mlsanity.com/paper/2409.13514/) (2024)

## Abstract (arXiv)

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 Oleft(|E| + s |Sigma| |Q| Tmax log|Sigma|right), where Q is the set of states and Tmax is the size of the largest connected component of failure transitions. When the failure transition topology satisfies a condition exemplified by CRFs, the Tmax 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 Oleft(|E| + |Sigma| |Q| min(1,sπmax) right), where πmax is the size of the longest failure path.