论文标题
加权下降自动机的算法
Algorithms for Weighted Pushdown Automata
论文作者
论文摘要
加权下调自动机（WPDA）是许多自然语言处理任务的核心，例如基于语法的统计计算机翻译和基于过渡的依赖性解析。由于大多数现有的动态编程算法都是为无上下文语法（CFGS）而设计的，因此PDA的算法通常诉诸PDA-TO-CFG转换。在本文中，我们开发了直接在WPDA上运行的新型算法。我们的算法灵感来自Lang的算法，但使用更一般的下降自动机定义，并将空间需求减少$ |γ| $（堆栈字母的大小），或者将运行时减少超过$ | q | $ $（国家数量）。当在与Lang的算法的同一类PDA上运行时，我们的算法既可以更高的效率$ |γ| $，又更高的时间效率效率为$ | q |。 \ cdot |γ| $。
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 |Γ|$.
