# RNN Generalization to Omega-Regular Languages

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 31 references that are in the map.
- First posted on arXiv 2 Sep 2025.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [On the Convergence of Adam and Beyond](https://mlsanity.com/paper/1904.09237/) (2019)
- [Neural Networks and the Chomsky Hierarchy](https://mlsanity.com/paper/2207.02098/) (2022)
- [Extracting Automata from Recurrent Neural Networks Using Queries and Counterexamples](https://mlsanity.com/paper/1711.09576/) (2017)
- [A Formal Hierarchy of RNN Architectures](https://mlsanity.com/paper/2004.08500/) (2020)
- [Teaching Temporal Logics to Neural Networks](https://mlsanity.com/paper/2003.04218/) (2020)
- [Why Warmup the Learning Rate? Underlying Mechanisms and Improvements](https://mlsanity.com/paper/2406.09405/) (2024)
- [Training Neural Networks as Recognizers of Formal Languages](https://mlsanity.com/paper/2411.07107/) (2024)
- [From Spot 2.0 to Spot 2.10: What's New?](https://mlsanity.com/paper/2206.11366/) (2022)
- [Neural Circuit Synthesis from Specification Patterns](https://mlsanity.com/paper/2107.11864/) (2021)
- [Extracting Finite Automata from RNNs Using State Merging](https://mlsanity.com/paper/2201.12451/) (2022)
- [Neural Model Checking](https://mlsanity.com/paper/2410.23790/) (2024)
- [Learning Finite Linear Temporal Logic Specifications with a Specialized Neural Operator](https://mlsanity.com/paper/2111.04147/) (2021)
- [Analyzing B"uchi Automata with Graph Neural Networks](https://mlsanity.com/paper/2206.09619/) (2022)
- [On Efficiently Representing Regular Languages as RNNs](https://mlsanity.com/paper/2402.15814/) (2024)

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

- [Logic-Gated Time-Shared Feedforward Networks for Alternating Finite Automata: Exact Simulation and Learnability](https://mlsanity.com/paper/2604.01228/) (2026)

## Abstract (arXiv)

B"uchi automata (BAs) recognize ω-regular languages defined by formal specifications like linear temporal logic (LTL) and are commonly used in the verification of reactive systems. However, BAs face scalability challenges when handling and manipulating complex system behaviors. As neural networks are increasingly used to address these scalability challenges in areas like model checking, investigating their ability to generalize beyond training data becomes necessary. This work presents the first study investigating whether recurrent neural networks (RNNs) can generalize to ω-regular languages derived from LTL formulas. We train RNNs on ultimately periodic ω-word sequences to replicate target BA behavior and evaluate how well they generalize to out-of-distribution sequences. Through experiments on LTL formulas corresponding to deterministic automata of varying structural complexity, from 3 to over 100 states, we show that RNNs achieve high accuracy on their target ω-regular languages when evaluated on sequences up to 8 × longer than training examples, with 92.6% of tasks achieving perfect or near-perfect generalization. These results establish the feasibility of neural approaches for learning complex ω-regular languages, suggesting their potential as components in neurosymbolic verification methods.