# Recurrent Neural Networks as Weighted Language Recognizers

arXiv: https://arxiv.org/abs/1711.05408 · HTML: https://mlsanity.com/paper/1711.05408/

## Key facts

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

## Built on by (most cited first, 30 of 30)

- [Large Language Models](https://mlsanity.com/paper/2307.05782/) (2023)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [NeuroLogic A*esque Decoding: Constrained Text Generation with Lookahead Heuristics](https://mlsanity.com/paper/2112.08726/) (2021)
- [Calibrating Sequence likelihood Improves Conditional Language Generation](https://mlsanity.com/paper/2210.00045/) (2022)
- [Statistically Meaningful Approximation: a Case Study on Approximating Turing Machines with Transformers](https://mlsanity.com/paper/2107.13163/) (2021)
- [Tighter Bounds on the Expressivity of Transformer Encoders](https://mlsanity.com/paper/2301.10743/) (2023)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Learning Universal Predictors](https://mlsanity.com/paper/2401.14953/) (2024)
- [A Well-Composed Text is Half Done! Composition Sampling for Diverse Conditional Generation](https://mlsanity.com/paper/2203.15108/) (2022)
- [Universal Length Generalization with Turing Programs](https://mlsanity.com/paper/2407.03310/) (2024)
- [Permute-and-Flip: An optimally stable and watermarkable decoder for LLMs](https://mlsanity.com/paper/2402.05864/) (2024)
- [Practical Computational Power of Linear Transformers and Their Recurrent and Self-Referential Extensions](https://mlsanity.com/paper/2310.16076/) (2023)
- [Autoregressive Large Language Models are Computationally Universal](https://mlsanity.com/paper/2410.03170/) (2024)
- [Language Models are Symbolic Learners in Arithmetic](https://mlsanity.com/paper/2410.15580/) (2024)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)
- [Recurrent Neural Language Models as Probabilistic Finite-state Automata](https://mlsanity.com/paper/2310.05161/) (2023)
- [Predictive Querying for Autoregressive Neural Sequence Models](https://mlsanity.com/paper/2210.06464/) (2022)
- [Positional Encoding Helps Recurrent Neural Networks Handle a Large Vocabulary](https://mlsanity.com/paper/2402.00236/) (2024)
- [Unlocking Anticipatory Text Generation: A Constrained Approach for Large Language Models Decoding](https://mlsanity.com/paper/2312.06149/) (2023)
- [Emergence of the Primacy Effect in Structured State-Space Models](https://mlsanity.com/paper/2502.13729/) (2025)
- [Understanding Robust Generalization in Learning Regular Languages](https://mlsanity.com/paper/2202.09717/) (2022)
- [A Tensor Decomposition Perspective on Second-order RNNs](https://mlsanity.com/paper/2406.05045/) (2024)
- [Neural Networks Generalize on Low Complexity Data](https://mlsanity.com/paper/2409.12446/) (2024)
- [An Algebraic View of the Expressivity of Recurrent Language Models](https://mlsanity.com/paper/2606.01765/) (2026)
- [On the Depth between Beam Search and Exhaustive Search for Text Generation](https://mlsanity.com/paper/2308.13696/) (2023)
- [On the Representational Capacity of Recurrent Neural Language Models](https://mlsanity.com/paper/2310.12942/) (2023)
- [Aligning Brain Activity with Advanced Transformer Models: Exploring the Role of Punctuation in Semantic Processing](https://mlsanity.com/paper/2501.06278/) (2025)
- [Learning Transductions and Alignments with RNN Seq2seq Models](https://mlsanity.com/paper/2303.06841/) (2023)
- [Exploring Learnability in Memory-Augmented Recurrent Neural Networks: Precision, Stability, and Empirical Insights](https://mlsanity.com/paper/2410.03154/) (2024)
- [LTL Verification of Memoryful Neural Agents](https://mlsanity.com/paper/2503.02512/) (2025)

## 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.