# Algorithms for Weighted Pushdown Automata

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 39 references that are in the map.
- First posted on arXiv 13 Oct 2022.

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

- [Recurrent Neural Network Grammars](https://mlsanity.com/paper/1602.07776/) (2016)
- [Transition-Based Dependency Parsing with Stack Long Short-Term Memory](https://mlsanity.com/paper/1505.08075/) (2015)
- [Stack-Pointer Networks for Dependency Parsing](https://mlsanity.com/paper/1805.01087/) (2018)
- [Globally Normalized Transition-Based Neural Networks](https://mlsanity.com/paper/1603.06042/) (2016)
- [Left-to-Right Dependency Parsing with Pointer Networks](https://mlsanity.com/paper/1903.08445/) (2019)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Learning Context-Free Languages with Nondeterministic Stack RNNs](https://mlsanity.com/paper/2010.04674/) (2020)
- [Structured Training for Neural Network Transition-Based Parsing](https://mlsanity.com/paper/1506.06158/) (2015)
- [Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Set](https://mlsanity.com/paper/1708.09403/) (2017)

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

- [On Parsing as Tagging](https://mlsanity.com/paper/2211.07344/) (2022)

## Abstract (arXiv)

Weighted pushdown automata (WPDAs) are at the core of many natural language processing tasks, like syntax-based statistical machine translation and transition-based dependency parsing. As most existing dynamic programming algorithms are designed for context-free grammars (CFGs), algorithms for PDAs often resort to a PDA-to-CFG conversion. In this paper, we develop novel algorithms that operate directly on WPDAs. Our algorithms are inspired by Lang's algorithm, but use a more general definition of pushdown automaton and either reduce the space requirements by a factor of |Gamma| (the size of the stack alphabet) or reduce the runtime by a factor of more than |Q| (the number of states). When run on the same class of PDAs as Lang's algorithm, our algorithm is both more space-efficient by a factor of |Gamma| and more time-efficient by a factor of |Q| · |Gamma|.