mlsanityData to 7 Oct 2026

Formal Language Theory Meets Modern NLP

arXiv 2102.10094 ↗First posted 19 Feb 2021cs.CLcited by 9

Not on the map. Why?

Abstract (arXiv)

NLP is deeply intertwined with the formal study of language, both conceptually and historically. Arguably, this connection goes all the way back to Chomsky's Syntactic Structures in 1957. It also still holds true today, with a strand of recent works building formal analysis of modern neural networks methods in terms of formal languages. In this document, I aim to explain background about formal languages as they relate to this recent work. I will by necessity ignore large parts of the rich history of this field, instead focusing on concepts connecting to modern deep learning-based NLP.

Key facts. Cited by 9 papers in the map (data through 7 Oct 2026). Builds on 26 of its 69 references that are in the map. First posted on arXiv 19 Feb 2021.

Builds on

26 of 69 references.

References · 26

  1. 2017Attention Is All You Needcited by 59,932
  2. 2019Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformercited by 14,491
  3. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,337
  4. 2014Neural Turing Machinescited by 630
  5. 2019Theoretical Limitations of Self-Attention in Neural Sequence Modelscited by 286
  6. 2015Visualizing and Understanding Recurrent Networkscited by 158
  7. 2019An Exponential Learning Rate Schedule for Deep Learningcited by 121
  8. 2018On the Practical Computational Power of Finite Precision RNNs for Language Recognitioncited by 117
  9. 2019Asymmetric Valleys: Beyond Sharp and Flat Local Minimacited by 90
  10. 2020A Formal Hierarchy of RNN Architecturescited by 61
  11. 2015Learning to Transduce with Unbounded Memorycited by 54
  12. 2019Sequential Neural Networks as Automatacited by 54
14 more
  1. 2019LSTM Networks Can Perform Dynamic Countingcited by 45
  2. 2019Memory-Augmented Recurrent Neural Networks Can Learn Generalized Dyck Languagescited by 31
  3. 2018Rational Recurrencescited by 18
  4. 2020A Survey of Neural Networks and Formal Languagescited by 17
  5. 2020On the Linguistic Capacity of Real-Time Counter Automatacited by 16
  6. 2018Connecting Weighted Automata and Recurrent Neural Networks through Spectral Learningcited by 15
  7. 2020Learning Context-Free Languages with Nondeterministic Stack RNNscited by 15
  8. 2018Context-Free Transductions with Neural Stackscited by 14
  9. 2020On the Ability and Limitations of Transformers to Recognize Formal Languagescited by 12
  10. 2018SoPa: Bridging CNNs, RNNs, and Weighted Finite-State Machinescited by 8
  11. 2019Finding Syntactic Representations in Neural Stackscited by 4
  12. 2020Distance and Equivalence between Finite State Machines and Recurrent Neural Networks: Computational resultscited by 2
  13. 2020How LSTM Encodes Syntax: Exploring Context Vectors and Semi-Quantization on Natural Textcited by 2
  14. 2021Stronger Separation of Analog Neuron Hierarchy by Deterministic Context-Free Languagescited by 1

Built on by

Cited by year

Citing papers per year: 2021: 2; 2022: 2; 2023: 3; 2024: 2.

9 papers.

  1. 2021Saturated Transformers are Constant-Depth Threshold Circuitscited by 137
  2. 2023What Formal Languages Can Transformers Express? A Surveycited by 120
  3. 2022What Makes Instruction Learning Hard? An Investigation and a New Challenge in a Synthetic Environmentcited by 9
  4. 2023Evaluating Transformer's Ability to Learn Mildly Context-Sensitive Languagescited by 2
  5. 2024Extracting Moore Machines from Transformers using Queries and Counterexamplescited by 2
  6. 2022Implementation of general formal translatorscited by 1
  7. 2021Learning and Generalization in RNNscited by 0
  8. 2023Nondeterministic Stacks in Neural Networkscited by 0
  9. 2024Never Reset Again: A Mathematical Framework for Continual Inference in Recurrent Neural Networkscited by 0