# Context-Free Transductions with Neural Stacks

arXiv: https://arxiv.org/abs/1809.02836 · HTML: https://mlsanity.com/paper/1809.02836/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Sep 2018.

## Built on by (most cited first, 14 of 14)

- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Mission: Impossible Language Models](https://mlsanity.com/paper/2401.06416/) (2024)
- [Transformers Can Represent n-gram Language Models](https://mlsanity.com/paper/2404.14994/) (2024)
- [What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languages](https://mlsanity.com/paper/2406.04289/) (2024)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [Lower Bounds on the Expressivity of Recurrent Neural Language Models](https://mlsanity.com/paper/2405.19222/) (2024)
- [State-Regularized Recurrent Neural Networks to Extract Automata and Explain Predictions](https://mlsanity.com/paper/2212.05178/) (2022)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [On the Representational Capacity of Recurrent Neural Language Models](https://mlsanity.com/paper/2310.12942/) (2023)
- [On Efficiently Representing Regular Languages as RNNs](https://mlsanity.com/paper/2402.15814/) (2024)
- [Enhancing Length Extrapolation in Sequential Models with Pointer-Augmented Neural Memory](https://mlsanity.com/paper/2404.11870/) (2024)

## Abstract (arXiv)

This paper analyzes the behavior of stack-augmented recurrent neural network (RNN) models. Due to the architectural similarity between stack RNNs and pushdown transducers, we train stack RNN models on a number of tasks, including string reversal, context-free language modelling, and cumulative XOR evaluation. Examining the behavior of our networks, we show that stack-augmented RNNs can discover intuitive stack-based strategies for solving our tasks. However, stack RNNs are more difficult to train than classical architectures such as LSTMs. Rather than employ stack-based strategies, more complex networks often find approximate solutions by using the stack as unstructured memory.