Algorithms for Weighted Pushdown Automata
Alexandra Butoi, Brian DuSell, Tim Vieira, Ryan Cotterell, David Chiang · 2022
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 |Γ| (the size of the stack alphabet) or reduce the runtime by a factor of more than |𝑄| (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 |Γ| and more time-efficient by a factor of |𝑄| • |Γ|.