# On Efficiently Representing Regular Languages as RNNs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 36 references that are in the map.
- First posted on arXiv 24 Feb 2024.

## Builds on (most cited first, 13 of 13)

- [Pre-trained Models for Natural Language Processing: A Survey](https://mlsanity.com/paper/2003.08271/) (2020)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [Saturated Transformers are Constant-Depth Threshold Circuits](https://mlsanity.com/paper/2106.16213/) (2021)
- [Self-Attention Networks Can Process Bounded Hierarchical Languages](https://mlsanity.com/paper/2105.11115/) (2021)
- [RecurrentGPT: Interactive Generation of (Arbitrarily) Long Text](https://mlsanity.com/paper/2305.13304/) (2023)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [RNNs can generate bounded hierarchical languages with optimal memory](https://mlsanity.com/paper/2010.07515/) (2020)
- [Sequential Neural Networks as Automata](https://mlsanity.com/paper/1906.01615/) (2019)
- [On the Computational Power of RNNs](https://mlsanity.com/paper/1906.06349/) (2019)
- [A Measure-Theoretic Characterization of Tight Language Models](https://mlsanity.com/paper/2212.10502/) (2022)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Context-Free Transductions with Neural Stacks](https://mlsanity.com/paper/1809.02836/) (2018)
- [The Surprising Computational Power of Nondeterministic Stack RNNs](https://mlsanity.com/paper/2210.01343/) (2022)

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

- [RNN Generalization to Omega-Regular Languages](https://mlsanity.com/paper/2509.02491/) (2025)

## Abstract (arXiv)

Recent work by Hewitt et al. (2020) provides an interpretation of the empirical success of recurrent neural networks (RNNs) as language models (LMs). It shows that RNNs can efficiently represent bounded hierarchical structures that are prevalent in human language. This suggests that RNNs' success might be linked to their ability to model hierarchy. However, a closer inspection of Hewitt et al.'s (2020) construction shows that it is not inherently limited to hierarchical structures. This poses a natural question: What other classes of LMs can RNNs efficiently represent? To this end, we generalize Hewitt et al.'s (2020) construction and show that RNNs can efficiently represent a larger class of LMs than previously claimed -- specifically, those that can be represented by a pushdown automaton with a bounded stack and a specific stack update function. Altogether, the efficiency of representing this diverse class of LMs with RNN LMs suggests novel interpretations of their inductive bias.