Algorithms for Weighted Pushdown Automata

2022-10-13 · Alexandra Butoi, Brian DuSell, Tim Vieira, Ryan Cotterell, David Chiang

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| \cdot |\Gamma|$.

📄 PDF Abstract BibTeX arXiv:2210.06884

Code (1)

rycolab/wpda 공식 구현

Tasks

Dependency Parsing Machine TranslationTransition-Based Dependency Parsing

Efficient Algorithms for Recognizing Weighted Tree-Adjoining Languages

2023-10-23 · Alexandra Butoi, Tim Vieira, Ryan Cotterell, David Chiang

The class of tree-adjoining languages can be characterized by various two-level formalisms, consisting of a context-free grammar (CFG) or pushdown automaton (PDA) controlling another CFG or PDA. These four formalisms are…

TAG

Prediction of Infinite Words with Automata

2016-03-08 · Tim Smith

In the classic problem of sequence prediction, a predictor receives a sequence of values from an emitter and tries to guess the next value before it appears. The predictor masters the emitter if there is a point after wh…

Prediction

Pushdown Automata in Statistical Machine Translation

2014-09-01 · CL 2014 9 · Cyril Allauzen, Bill Byrne, Adri{\`a} de Gispert, Gonzalo Iglesias 외

Language Modelling Machine Translation Translation

Pushdown Reward Machines for Reinforcement Learning

2025-08-09 · Giovanni Varricchione, Toryn Q. Klassen, Natasha Alechina, Mehdi Dastani 외 arxiv

Reward machines (RMs) are automata structures that encode (non-Markovian) reward functions for reinforcement learning (RL). RMs can reward any behaviour representable in regular languages and, when paired with RL algorit…

Reinforcement Learning

On the Computational Power of RNNs

2019-06-14 · Samuel A. Korsky, Robert C. Berwick

Recent neural network architectures such as the basic recurrent neural network (RNN) and Gated Recurrent Unit (GRU) have gained prominence as end-to-end learning architectures for natural language processing tasks. But w…