mlsanityData to 7 Oct 2026

On the Computational Power of RNNs

arXiv 1906.06349 ↗First posted 14 Jun 2019cs.CL cs.LGcited by 35

Not on the map. Why?

Abstract (arXiv)

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 what is the computational power of such systems? We prove that finite precision RNNs with one hidden layer and ReLU activation and finite precision GRUs are exactly as computationally powerful as deterministic finite automata. Allowing arbitrary precision, we prove that RNNs with one hidden layer and ReLU activation are at least as computationally powerful as pushdown automata. If we also allow infinite precision, infinite edge weights, and nonlinear output activation functions, we prove that GRUs are at least as computationally powerful as pushdown automata. All results are shown constructively.

Key facts. Cited by 35 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Jun 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 2; 2023: 3; 2024: 9; 2025: 9; 2026: 7.

35 papers.

Sort:

By area:

  1. 2022Neural Networks and the Chomsky Hierarchycited by 214
  2. 2021Self-Attention Networks Can Process Bounded Hierarchical Languagescited by 105
  3. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 101
  4. 2024Theoretical Foundations of Deep Selective State-Space Modelscited by 73
  5. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 68
  6. 2025How Linguistics Learned to Stop Worrying and Love the Language Modelscited by 50
  7. 2024Separations in the Representational Capabilities of Transformers and Recurrent Architecturescited by 29
  8. 2024On the Representational Capacity of Neural Language Models with Chain-of-Thought Reasoningcited by 26
  9. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  10. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  11. 2024Autoregressive Large Language Models are Computationally Universalcited by 14
  12. 2024Rethinking Transformers in Solving POMDPscited by 9
23 more
  1. 2021Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanationscited by 7
  2. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  3. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  4. 2025Fixed-Point RNNs: Interpolating from Diagonal to Densecited by 5
  5. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  6. 2024A Tensor Decomposition Perspective on Second-order RNNscited by 3
  7. 2021Synthesizing Context-free Grammars from Recurrent Neural Networks (Extended Version)cited by 2
  8. 2025A Constructive Framework for Nondeterministic Automata via Time-Shared, Depth-Unrolled Feedforward Networkscited by 2
  9. 2026An Algebraic View of the Expressivity of Recurrent Language Modelscited by 2
  10. 2023On the Representational Capacity of Recurrent Neural Language Modelscited by 1
  11. 2024On Efficiently Representing Regular Languages as RNNscited by 1
  12. 2026Universal computation is intrinsic to language model decodingcited by 1
  13. 2021Learning and Generalization in RNNscited by 0
  14. 2025Learning Model Successorscited by 0
  15. 2025Language models as tools for investigating the distinction between possible and impossible natural languagescited by 0
  16. 2025Large language models have learned to use languagecited by 0
  17. 2025Large language models are not about natural languagecited by 0
  18. 2025Linguists should learn to love speech-based deep learning modelscited by 0
  19. 2026Are Language Models Models?cited by 0
  20. 2026Across the Levels of Analysis: Explaining Predictive Processing in Humans Requires More Than Machine-Estimated Probabilitiescited by 0
  21. 2026You Can't Fight in Here! This is BBS!cited by 0
  22. 2026Not-So-Strange Love: Language Models and Generative Linguistic Theories are More Compatible than They Appearcited by 0
  23. 2026An Irreducible Quantum Advantage in Aligning World Models with Realitycited by 0