mlsanityData to 7 Oct 2026

A Survey of Neural Networks and Formal Languages

arXiv 2006.01338 ↗First posted 2 Jun 2020cs.CLcited by 17

Not on the map. Why?

Abstract (arXiv)

This report is a survey of the relationships between various state-of-the-art neural network architectures and formal languages as, for example, structured by the Chomsky Language Hierarchy. Of particular interest are the abilities of a neural architecture to represent, recognize and generate words from a specific language by learning from samples of the language.

Key facts. Cited by 17 papers in the map (data through 7 Oct 2026). First posted on arXiv 2 Jun 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

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

17 papers.

Sort:

By area:

  1. 2022Neural Networks and the Chomsky Hierarchycited by 214
  2. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  3. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 114
  4. 2024Counting Ability of Large Language Models and Impact of Tokenizationcited by 29
  5. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
  6. 2024Position: Understanding LLMs Requires More Than Statistical Generalizationcited by 20
  7. 2021Formal Language Theory Meets Modern NLPcited by 9
  8. 2025Tokenization Constraints in LLMs: A Study of Symbolic and Arithmetic Reasoning Limitscited by 9
  9. 2024Lower Bounds on the Expressivity of Recurrent Neural Language Modelscited by 4
  10. 2022Understanding Robust Generalization in Learning Regular Languagescited by 3
  11. 2023State space models can express n-gram languagescited by 3
  12. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2
5 more
  1. 2025Emergent Stack Representations in Modeling Counter Languages Using Transformerscited by 2
  2. 2026An expressivity analysis of hierarchical modelling in deep transformers via bounded-depth grammarscited by 1
  3. 2024Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insightscited by 0
  4. 2025Exploring Major Transitions in the Evolution of Biological Cognition With Artificial Neural Networkscited by 0
  5. 2026On the Expressive Power of Transformerscited by 0