Algorithms for Weighted Pushdown Automata
This work addresses efficiency bottlenecks in natural language processing tasks like machine translation and parsing, offering incremental improvements over prior algorithms.
The paper tackles the problem of inefficient algorithms for weighted pushdown automata (WPDAs) by developing novel algorithms that operate directly on WPDAs, reducing space requirements by a factor of |Γ| and runtime by a factor of more than |Q| compared to existing methods.
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 $|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 $|Γ|$ and more time-efficient by a factor of $|Q| \cdot |Γ|$.