mlsanityData to 14 Oct 2026

Recurrent Neural Networks as Weighted Language Recognizers

arXiv 1711.05408 ↗First posted 15 Nov 2017cs.FL cs.CC cs.CLcited by 30

Not on the map. Why?

Abstract (arXiv)

We investigate the computational complexity of various problems for simple recurrent neural networks (RNNs) as formal models for recognizing weighted languages. We focus on the single-layer, ReLU-activation, rational-weight RNNs with softmax, which are commonly used in natural language processing applications. We show that most problems for such RNNs are undecidable, including consistency, equivalence, minimization, and the determination of the highest-weighted string. However, for consistent RNNs the last problem becomes decidable, although the solution length can surpass all computable bounds. If additionally the string is limited to polynomial length, the problem becomes NP-complete and APX-hard. In summary, this shows that approximations and heuristic algorithms are necessary in practical applications of those RNNs.

Key facts. Cited by 30 papers in the map (data through 14 Oct 2026). First posted on arXiv 15 Nov 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

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

30 papers.

Sort:

By area:

  1. 2023Large Language Modelscited by 780
  2. 2022Neural Networks and the Chomsky Hierarchycited by 217
  3. 2021NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristicscited by 154
  4. 2022Calibrating Sequence likelihood Improves Conditional Language Generationcited by 121
  5. 2021Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformerscited by 102
  6. 2023Tighter Bounds on the Expressivity of Transformer Encoderscited by 66
  7. 2022A Measure-Theoretic Characterization of Tight Language Modelscited by 33
  8. 2024Learning Universal Predictorscited by 31
  9. 2022A Well-Composed Text is Half Done! Composition Sampling for Diverse Conditional Generationcited by 28
  10. 2024Universal Length Generalization with Turing Programscited by 25
  11. 2024Permute-and-Flip: An optimally stable and watermarkable decoder for LLMscited by 22
  12. 2023Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensionscited by 20
18 more
  1. 2024Autoregressive Large Language Models are Computationally Universalcited by 15
  2. 2024Language Models are Symbolic Learners in Arithmeticcited by 11
  3. 2022The Surprising Computational Power of Nondeterministic Stack RNNscited by 6
  4. 2023Recurrent Neural Language Models as Probabilistic Finite-state Automatacited by 6
  5. 2022Predictive Querying for Autoregressive Neural Sequence Modelscited by 5
  6. 2024Positional Encoding Helps Recurrent Neural Networks Handle a Large Vocabularycited by 5
  7. 2023Unlocking Anticipatory Text Generation: A Constrained Approach for Large Language Models Decodingcited by 4
  8. 2025Emergence of the Primacy Effect in Structured State-Space Modelscited by 4
  9. 2022Understanding Robust Generalization in Learning Regular Languagescited by 3
  10. 2024A Tensor Decomposition Perspective on Second-order RNNscited by 3
  11. 2024Neural Networks Generalize on Low Complexity Datacited by 3
  12. 2023On the Depth between Beam Search and Exhaustive Search for Text Generationcited by 2
  13. 2026An Algebraic View of the Expressivity of Recurrent Language Modelscited by 2
  14. 2023On the Representational Capacity of Recurrent Neural Language Modelscited by 1
  15. 2025Aligning Brain Activity with Advanced Transformer Models: Exploring the Role of Punctuation in Semantic Processingcited by 1
  16. 2023Learning Transductions and Alignments with RNN Seq2seq Modelscited by 0
  17. 2024Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insightscited by 0
  18. 2025LTL Verification of Memoryful Neural Agentscited by 0