2022/10/13 by Alexandra Butoi, Butoi, Alexandra, Brian DuSell +7
Computer Science · #Computation and Language (cs.CL) #FOS: Computer and information sciences #Natural Language Processing Techniques #Network Packet Processing and Optimization #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2210.06884
openalex publication_date 2022/10/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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| ⋅ |Γ|.