# Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languages

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

## Key facts

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

## Built on by (most cited first, 30 of 31)

- [Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approach](https://mlsanity.com/paper/2502.05171/) (2025)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Dynamic Cheatsheet: Test-Time Learning with Adaptive Memory](https://mlsanity.com/paper/2504.07952/) (2025)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [In-Context Language Learning: Architectures and Algorithms](https://mlsanity.com/paper/2401.12973/) (2024)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [Separations in the Representational Capabilities of Transformers and Recurrent Architectures](https://mlsanity.com/paper/2406.09347/) (2024)
- [Minimum Description Length Recurrent Neural Networks](https://mlsanity.com/paper/2111.00600/) (2021)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Pushdown Layers: Encoding Recursive Structure in Transformer Language Models](https://mlsanity.com/paper/2310.19089/) (2023)
- [Learning Hierarchical Structures with Differentiable Nondeterministic Stacks](https://mlsanity.com/paper/2109.01982/) (2021)
- [On the Expressiveness and Length Generalization of Selective State-Space Models on Regular Languages](https://mlsanity.com/paper/2412.19350/) (2024)
- [Emergent Word Order Universals from Cognitively-Motivated Language Models](https://mlsanity.com/paper/2402.12363/) (2024)
- [Can RNNs learn Recursive Nested Subject-Verb Agreements?](https://mlsanity.com/paper/2101.02258/) (2021)
- [Formal Language Theory Meets Modern NLP](https://mlsanity.com/paper/2102.10094/) (2021)
- [Recognizing and Verifying Mathematical Equations using Multiplicative Differential Neural Units](https://mlsanity.com/paper/2104.02899/) (2021)
- [Causal Transformers Perform Below Chance on Recursive Nested Constructions, Unlike Humans](https://mlsanity.com/paper/2110.07240/) (2021)
- [Feature Interactions Reveal Linguistic Structure in Language Models](https://mlsanity.com/paper/2306.12181/) (2023)
- [Can Interpretation Predict Behavior on Unseen Data?](https://mlsanity.com/paper/2507.06445/) (2025)
- [Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanations](https://mlsanity.com/paper/2112.09174/) (2021)
- [Theoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networks](https://mlsanity.com/paper/2304.03639/) (2023)
- [Benchmarking Neural Network Generalization for Grammar Induction](https://mlsanity.com/paper/2308.08253/) (2023)
- [A Transformer with Stack Attention](https://mlsanity.com/paper/2405.04515/) (2024)
- [Emergent Stack Representations in Modeling Counter Languages Using Transformers](https://mlsanity.com/paper/2502.01432/) (2025)
- [State-Space Constraints Can Improve the Generalisation of the Differentiable Neural Computer to Input Sequences With Unseen Length](https://mlsanity.com/paper/2110.09138/) (2021)
- [On the Emergence of Syntax by Means of Local Interaction](https://mlsanity.com/paper/2604.17857/) (2026)
- [Enhancing Reinforcement Learning with discrete interfaces to learn the Dyck Language](https://mlsanity.com/paper/2110.14350/) (2021)
- [Nondeterministic Stacks in Neural Networks](https://mlsanity.com/paper/2304.12955/) (2023)
- [Enhancing Length Extrapolation in Sequential Models with Pointer-Augmented Neural Memory](https://mlsanity.com/paper/2404.11870/) (2024)

## Abstract (arXiv)

We introduce three memory-augmented Recurrent Neural Networks (MARNNs) and explore their capabilities on a series of simple language modeling tasks whose solutions require stack-based mechanisms. We provide the first demonstration of neural networks recognizing the generalized Dyck languages, which express the core of what it means to be a language with hierarchical structure. Our memory-augmented architectures are easy to train in an end-to-end fashion and can learn the Dyck languages over as many as six parenthesis-pairs, in addition to two deterministic palindrome languages and the string-reversal transduction task, by emulating pushdown automata. Our experiments highlight the increased modeling capacity of memory-augmented models over simple RNNs, while inflecting our understanding of the limitations of these models.