%0 Conference Proceedings
%T Algorithms for Weighted Pushdown Automata
%A Butoi, Alexandra
%A DuSell, Brian
%A Vieira, Tim
%A Cotterell, Ryan
%A Chiang, David
%S Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing
%D 2022
%8 December
%I Association for Computational Linguistics
%C Abu Dhabi, United Arab Emirates
%F butoi-etal-2022-algorithms
%X 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| x |Gamma|.
%R 10.18653/v1/2022.emnlp-main.656
%U https://aclanthology.org/2022.emnlp-main.656
%U https://doi.org/10.18653/v1/2022.emnlp-main.656
%P 9669-9680