Algorithms for Weighted Pushdown Automata
Not on the map. Why?
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|.
Key facts. Cited by 1 paper 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
9 of 39 references.
References · 9
- 2016Recurrent Neural Network Grammarscited by 109
- 2015Transition-Based Dependency Parsing with Stack Long Short-Term Memorycited by 45
- 2018Stack-Pointer Networks for Dependency Parsingcited by 36
- 2016Globally Normalized Transition-Based Neural Networkscited by 26
- 2019Left-to-Right Dependency Parsing with Pointer Networkscited by 21
- 2021Learning Hierarchical Structures with Differentiable Nondeterministic Stackscited by 16
- 2020Learning Context-Free Languages with Nondeterministic Stack RNNscited by 15
- 2015Structured Training for Neural Network Transition-Based Parsingcited by 11
- 2017Fast(er) Exact Decoding and Global Training for Transition-Based Dependency Parsing via a Minimal Feature Setcited by 5
Built on by
Citing papers per year: 2022: 1.
1 paper.
- 2022On Parsing as Taggingcited by 0
- 2022On Parsing as Tagging14 Nov 2022