mlsanityData to 14 Oct 2026

On the Practical Computational Power of Finite Precision RNNs for Language Recognition

arXiv 1805.04908 ↗First posted 13 May 2018cs.LG cs.CL stat.MLcited by 117

Not on the map. Why?

Abstract (arXiv)

While Recurrent Neural Networks (RNNs) are famously known to be Turing complete, this relies on infinite precision in the states and unbounded computation time. We consider the case of RNNs with finite precision whose computation time is linear in the input length. Under these limitations, we show that different RNN variants have different computational power. In particular, we show that the LSTM and the Elman-RNN with ReLU activation are strictly stronger than the RNN with a squashing activation and the GRU. This is achieved because LSTMs and ReLU-RNNs can easily implement counting behavior. We show empirically that the LSTM does indeed learn to effectively use the counting mechanism.

Key facts. Cited by 117 papers in the map (data through 14 Oct 2026). First posted on arXiv 13 May 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 17; 2022: 14; 2023: 24; 2024: 18; 2025: 25; 2026: 19.

117 papers.

Sort:

By area:

  1. 2021How Attentive are Graph Attention Networks?cited by 835
  2. 2023Large Language Modelscited by 780
  3. 2022Neural Networks and the Chomsky Hierarchycited by 217
  4. 2021Thinking Like Transformerscited by 184
  5. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 139
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 124
  7. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  8. 2021Going Beyond Linear Transformers with Recurrent Fast Weight Programmerscited by 89
  9. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 86
  10. 2022Simplicity Bias in Transformers and their Ability to Learn Sparse Boolean Functionscited by 70
  11. 2022A Logic for Expressing Log-Precision Transformerscited by 67
  12. 2024Mechanistic Design and Scaling of Hybrid Architecturescited by 59
38 more
  1. 2025How Linguistics Learned to Stop Worrying and Love the Language Modelscited by 51
  2. 2023The Expressive Power of Transformers with Chain of Thoughtcited by 50
  3. 2023Memory Augmented Large Language Models are Computationally Universalcited by 47
  4. 2024The Expressive Capacity of State Space Models: A Formal Language Perspectivecited by 46
  5. 2024Mission: Impossible Language Modelscited by 32
  6. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 32
  7. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
  8. 2023Average-Hard Attention Transformers are Constant-Depth Uniform Threshold Circuitscited by 26
  9. 2024Mechanistic?cited by 25
  10. 2021Minimum Description Length Recurrent Neural Networkscited by 24
  11. 2024Training Neural Networks as Recognizers of Formal Languagescited by 24
  12. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  13. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  14. 2021Inducing Transformer's Compositional Generalization Ability via Auxiliary Sequence Prediction Taskscited by 19
  15. 2024Limits of Deep Learning: Sequence Modeling through the Lens of Complexity Theorycited by 19
  16. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  17. 2023Limits for Learning with Language Modelscited by 17
  18. 2021Exploring Transitivity in Neural NLI Models through Veridicalitycited by 15
  19. 2024Autoregressive Large Language Models are Computationally Universalcited by 15
  20. 2024Bridging the Empirical-Theoretical Gap in Neural Network Formal Language Learning Using Minimum Description Lengthcited by 14
  21. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  22. 2025Information Locality as an Inductive Bias for Neural Language Modelscited by 14
  23. 2022Benchmarking Compositionality with Formal Languagescited by 12
  24. 2023Counting and Algorithmic Generalization with Transformerscited by 12
  25. 2024Emergent Word Order Universals from Cognitively-Motivated Language Modelscited by 11
  26. 2024Can Transformers Learn n-gram Language Models?cited by 11
  27. 2023Human Behavioral Benchmarking: Numeric Magnitude Comparison Effects in Large Language Modelscited by 10
  28. 2021Can RNNs learn Recursive Nested Subject-Verb Agreements?cited by 9
  29. 2021Formal Language Theory Meets Modern NLPcited by 9
  30. 2025Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limitscited by 9
  31. 2022Mutual Exclusivity Training and Primitive Augmentation to Induce Compositionalitycited by 8
  32. 2023On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networkscited by 8
  33. 2025Meta-Learning Neural Mechanisms rather than Bayesian Priorscited by 8
  34. 2025Fast weight programming and linear transformers: from machine learning to neurobiologycited by 8
  35. 2026Why Are Linear RNNs More Parallelizable?cited by 8
  36. 2021Learning Bounded Context-Free-Grammar via LSTM and the Transformer:Difference and Explanationscited by 7
  37. 2022Exploring the Long-Term Generalization of Counting Behavior in RNNscited by 7
  38. 2023Introducing Rhetorical Parallelism Detection: A New Task with Datasets, Metrics, and Baselinescited by 7

50 most cited of 117 All 117 (JSON)