mlsanityData to 7 Oct 2026

Sequential Neural Networks as Automata

arXiv 1906.01615 ↗First posted 4 Jun 2019cs.CL cs.FL cs.LGcited by 54

Not on the map. Why?

Abstract (arXiv)

This work attempts to explain the types of computation that neural networks can perform by relating them to automata. We first define what it means for a real-time network with bounded precision to accept a language. A measure of network memory follows from this definition. We then characterize the classes of languages acceptable by various recurrent networks, attention, and convolutional networks. We find that LSTMs function like counter machines and relate convolutional networks to the subregular hierarchy. Overall, this work attempts to increase our understanding and ability to interpret neural networks through the lens of theory. These theoretical insights help explain neural computation, as well as the relationship between neural networks and natural language grammar.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

54 papers.

Sort:

By area:

  1. 2022Neural Networks and the Chomsky Hierarchycited by 214
  2. 2024Repeat After Me: Transformers are Better than State Space Models at Copyingcited by 208
  3. 2021Thinking Like Transformerscited by 182
  4. 2024The Illusion of State in State-Space Modelscited by 181
  5. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  6. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  7. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  8. 2024In-Context Language Learning: Architectures and Algorithmscited by 86
  9. 2023How Do Transformers Learn Topic Structure: Towards a Mechanistic Understandingcited by 85
  10. 2024Mission: Impossible Language Modelscited by 31
  11. 2024Transformers Can Represent n-gram Language Modelscited by 31
  12. 2023Transformers are uninterpretable with myopic methods: a case study with bounded Dyck grammarscited by 30
38 more
  1. 2021Sensitivity as a Complexity Measure for Sequence Classification Taskscited by 28
  2. 2024Language Models Need Inductive Biases to Count Inductivelycited by 25
  3. 2024Training Neural Networks as Recognizers of Formal Languagescited by 23
  4. 2025Implicit Language Models are RNNs: Balancing Parallelization and Expressivitycited by 21
  5. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  6. 2024What Languages are Easy to Language-Model? A Perspective from Learning Probabilistic Regular Languagescited by 20
  7. 2021Transformers Generalize Linearlycited by 19
  8. 2022Extracting Finite Automata from RNNs Using State Mergingcited by 17
  9. 2025Characterizing the Expressivity of Fixed-Precision Transformer Language Modelscited by 14
  10. 2024Learning Useful Representations of Recurrent Neural Network Weight Matricescited by 13
  11. 2021Formal Language Theory Meets Modern NLPcited by 9
  12. 2024Rethinking Transformers in Solving POMDPscited by 9
  13. 2023On the Computational Complexity and Formal Hierarchy of Second Order Recurrent Neural Networkscited by 8
  14. 2026Why Are Linear RNNs More Parallelizable?cited by 7
  15. 2026M2RNN: Non-Linear RNNs with Matrix-Valued States for Scalable Language Modelingcited by 7
  16. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  17. 2025Compositional Reasoning with Transformers, RNNs, and Chain of Thoughtcited by 6
  18. 2021The Limitations of Limited Context for Constituency Parsingcited by 5
  19. 2022Implicit N-grams Induced by Recurrencecited by 4
  20. 2023LUNA: A Model-Based Universal Analysis Framework for Large Language Modelscited by 4
  21. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  22. 2025Rethinking Addressing in Language Models via Contexualized Equivariant Positional Encodingcited by 4
  23. 2025Unraveling Syntax: Language Modeling and the Substructure of Grammarscited by 4
  24. 2023Theoretical Conditions and Empirical Failure of Bracket Counting on Long Sequences with Linear Recurrent Networkscited by 3
  25. 2024A Tensor Decomposition Perspective on Second-order RNNscited by 3
  26. 2024LLMs as Probabilistic Minimally Adequate Teachers for DFA Learningcited by 3
  27. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  28. 2025Continuity and Isolation Lead to Doubts or Dilemmas in Large Language Modelscited by 2
  29. 2026An Algebraic View of the Expressivity of Recurrent Language Modelscited by 2
  30. 2023On the Representational Capacity of Recurrent Neural Language Modelscited by 1
  31. 2024On Efficiently Representing Regular Languages as RNNscited by 1
  32. 2024An L^* Algorithm for Deterministic Weighted Regular Languagescited by 1
  33. 2025Three tiers of computation in transformers and in brain architecturescited by 1
  34. 2025Exact Learning of Arithmetic with Differentiable Agentscited by 1
  35. 2026On Subquadratic Architectures: From Applications to Principlescited by 1
  36. 2021Learning and Generalization in RNNscited by 0
  37. 2023Learning Transductions and Alignments with RNN Seq2seq Modelscited by 0
  38. 2024DeepCover: Advancing RNN Test Coverage and Online Error Prediction using State Machine Extractioncited by 0

50 most cited of 54 All 54 (JSON)